In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi. Intuitively, this concept measures how close adigraph is to a directed acyclic graph (DAG), in the sense that a DAG hascycle rank zero, while a complete digraph of order n with a self-loop ateach vertex has cycle rank n. The cycle rank of a directed graph is closely related to the tree-depth of an undirected graph and to the star height of a regular language. It has also found usein sparse matrix computations (see ) and logic.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Cycle rank (en)
- Rang cyclique (graphe orienté) (fr)
- Циклический ранг (ru)
- Циклічний ранг (uk)
|
rdfs:comment
| - In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi. Intuitively, this concept measures how close adigraph is to a directed acyclic graph (DAG), in the sense that a DAG hascycle rank zero, while a complete digraph of order n with a self-loop ateach vertex has cycle rank n. The cycle rank of a directed graph is closely related to the tree-depth of an undirected graph and to the star height of a regular language. It has also found usein sparse matrix computations (see ) and logic. (en)
- En théorie des graphes, le rang cyclique d'un graphe orienté est une mesure de la connexité introduite par Eggan et Büchi en 1963. Intuitivement, cette valeur mesure à quel point un graphe est presque acyclique : un graphe orienté acyclique a un rang cyclique de zéro, tandis qu'un digraphe complet d'ordre n (avec une boucle à chaque sommet) a un rang cyclique n. Le rang cyclique d'un graphe orienté est proche de la hauteur d'étoile des langages rationnels. (fr)
- Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и . Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами (см. статью ) и логике. (ru)
- Циклічний ранг орієнтованого графа — міра зв'язності орграфа, яку запропонували Егган і . Це поняття інтуїтивно відбиває, наскільки близький орграф до спрямованого ациклічного графа (САГ, англ. DAG), коли циклічний ранг САГ дорівнює нулю, тоді як повний орграф порядку n із петлями в кожній вершині має циклічний ранг n. Циклічний ранг орієнтованого графа тісно пов'язаний із деревною глибиною неорієнтованого графа та висотою ітерації регулярних мов. Циклічний ранг набув застосування в обчисленнях із розрідженими матрицями (див. статтю) та логіці. (uk)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
bot
| |
date
| |
fix-attempted
| |
has abstract
| - In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi. Intuitively, this concept measures how close adigraph is to a directed acyclic graph (DAG), in the sense that a DAG hascycle rank zero, while a complete digraph of order n with a self-loop ateach vertex has cycle rank n. The cycle rank of a directed graph is closely related to the tree-depth of an undirected graph and to the star height of a regular language. It has also found usein sparse matrix computations (see ) and logic. (en)
- En théorie des graphes, le rang cyclique d'un graphe orienté est une mesure de la connexité introduite par Eggan et Büchi en 1963. Intuitivement, cette valeur mesure à quel point un graphe est presque acyclique : un graphe orienté acyclique a un rang cyclique de zéro, tandis qu'un digraphe complet d'ordre n (avec une boucle à chaque sommet) a un rang cyclique n. Le rang cyclique d'un graphe orienté est proche de la hauteur d'étoile des langages rationnels. (fr)
- Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и . Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами (см. статью ) и логике. (ru)
- Циклічний ранг орієнтованого графа — міра зв'язності орграфа, яку запропонували Егган і . Це поняття інтуїтивно відбиває, наскільки близький орграф до спрямованого ациклічного графа (САГ, англ. DAG), коли циклічний ранг САГ дорівнює нулю, тоді як повний орграф порядку n із петлями в кожній вершині має циклічний ранг n. Циклічний ранг орієнтованого графа тісно пов'язаний із деревною глибиною неорієнтованого графа та висотою ітерації регулярних мов. Циклічний ранг набув застосування в обчисленнях із розрідженими матрицями (див. статтю) та логіці. (uk)
|
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |