Cycle rank (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20110607103148/http:/www.hpl.hp.com/personal/Robert_Schreiber/papers/1982%20Sparse%20Gaussian%20Elimination/p256-schreiber%5B1%5D.pdf http://www.hpl.hp.com/personal/Robert_Schreiber/papers/1982%20Sparse%20Gaussian%20Elimination/p256-schreiber%5B1%5D.pdf http://www.hermann-gruber.com/data/dmtcs12-revised.pdf http://www.hermann-gruber.com/data/icalp08.pdf http://www.eti.pg.gda.pl/katedry/kams/wwwkams/pdf/Cholesky_fmprg.pdf https://web.archive.org/web/20110716060800/http:/www.eti.pg.gda.pl/katedry/kams/wwwkams/pdf/Cholesky_fmprg.pdf |
| dbo:wikiPageID | 25646409 (xsd:integer) |
| dbo:wikiPageLength | 10316 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1000095110 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Nondeterministic_finite_automaton dbc:Graph_connectivity dbr:Approximation_algorithm dbr:Julius_Richard_Büchi dbr:Regular_languages dbr:Undirected_graph dbr:International_Colloquium_on_Automata,_Languages_and_Programming dbc:Graph_invariants dbr:Complete_graph dbr:Concatenation dbr:Connectivity_(graph_theory) dbr:Empty_word dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:Logic dbr:Michigan_Mathematical_Journal dbr:Adjacency_matrix dbr:Formal_language_theory dbr:Directed_graph dbr:Graph_theory dbr:Journal_of_the_ACM dbr:Tree-depth dbr:Regular_language dbr:ACM_Transactions_on_Mathematical_Software dbr:Cholesky_factorization dbr:Star_height dbr:Directed_acyclic_graph dbr:Sparse_matrix dbr:Circuit_rank dbr:Cartesian_product_of_graphs dbr:Set_(mathematics) dbr:Nested_dissection dbr:Outdegree dbr:Directed_path dbr:N-tuple dbr:Input_symbol dbr:Self-loop dbr:Strongly_connected |
| dbp:bot | InternetArchiveBot (en) |
| dbp:date | August 2017 (en) |
| dbp:fixAttempted | yes (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Dead_link dbt:For dbt:Harv dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Tmath dbt:Harvnb dbt:Graph_connectivity_sidebar |
| dcterms:subject | dbc:Graph_connectivity dbc:Graph_invariants |
| gold:hypernym | dbr:Measure |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| 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) |
| rdfs:label | Cycle rank (en) Rang cyclique (graphe orienté) (fr) Циклический ранг (ru) Циклічний ранг (uk) |
| owl:sameAs | freebase:Cycle rank yago-res:Cycle rank wikidata:Cycle rank dbpedia-fr:Cycle rank dbpedia-ru:Cycle rank dbpedia-uk:Cycle rank https://global.dbpedia.org/id/4jACT |
| prov:wasDerivedFrom | wikipedia-en:Cycle_rank?oldid=1000095110&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Cycle_rank |
| is dbo:wikiPageRedirects of | dbr:Ordered_chromatic_number dbr:Minimum_elimination_tree_height dbr:Rank_coloring dbr:Vertex_ranking dbr:Vertex_ranking_number |
| is dbo:wikiPageWikiLink of | dbr:Entanglement_(graph_measure) dbr:Circular_coloring dbr:Cholesky_decomposition dbr:List_of_NP-complete_problems dbr:Tree-depth dbr:Rank_(graph_theory) dbr:Star_height dbr:Circuit_rank dbr:Nested_dissection dbr:Ordered_chromatic_number dbr:Minimum_elimination_tree_height dbr:Rank_coloring dbr:Vertex_ranking dbr:Vertex_ranking_number |
| is foaf:primaryTopic of | wikipedia-en:Cycle_rank |