Cycle rank
http://dbpedia.org/resource/Cycle_rank an entity of type: Software
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.
rdf:langString
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.
rdf:langString
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и . Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами (см. статью ) и логике.
rdf:langString
Циклічний ранг орієнтованого графа — міра зв'язності орграфа, яку запропонували Егган і . Це поняття інтуїтивно відбиває, наскільки близький орграф до спрямованого ациклічного графа (САГ, англ. DAG), коли циклічний ранг САГ дорівнює нулю, тоді як повний орграф порядку n із петлями в кожній вершині має циклічний ранг n. Циклічний ранг орієнтованого графа тісно пов'язаний із деревною глибиною неорієнтованого графа та висотою ітерації регулярних мов. Циклічний ранг набув застосування в обчисленнях із розрідженими матрицями (див. статтю) та логіці.
rdf:langString
rdf:langString
Cycle rank
rdf:langString
Rang cyclique (graphe orienté)
rdf:langString
Циклический ранг
rdf:langString
Циклічний ранг
xsd:integer
25646409
xsd:integer
1000095110
rdf:langString
InternetArchiveBot
rdf:langString
August 2017
rdf:langString
yes
rdf:langString
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.
rdf:langString
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.
rdf:langString
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и . Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами (см. статью ) и логике.
rdf:langString
Циклічний ранг орієнтованого графа — міра зв'язності орграфа, яку запропонували Егган і . Це поняття інтуїтивно відбиває, наскільки близький орграф до спрямованого ациклічного графа (САГ, англ. DAG), коли циклічний ранг САГ дорівнює нулю, тоді як повний орграф порядку n із петлями в кожній вершині має циклічний ранг n. Циклічний ранг орієнтованого графа тісно пов'язаний із деревною глибиною неорієнтованого графа та висотою ітерації регулярних мов. Циклічний ранг набув застосування в обчисленнях із розрідженими матрицями (див. статтю) та логіці.
xsd:nonNegativeInteger
10316