Tree-depth (original) (raw)
In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star. (en) В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина графа измеряет, насколько граф далёк от дерева, глубина дерева измеряет, насколько граф далёк от звезды. (ru) У теорії графів деревна глибина зв'язного неорієнтованого графа G — це числовий інваріант G, мінімальна висота дерева Тремо для суперграфа графа G. Цей інваріант і близькі поняття зустрічаються під різними назвами в літературі, зокрема як число ранжування вершин, впорядковане хроматичне число і мінімальна висота виключення дерева. Поняття близьке також до таких понять, як циклічний ранг орієнтованих графів і висота ітерації мови регулярних мов. Інтуїтивно, якщо деревна ширина графа вимірює, наскільки граф далекий від дерева, деревна глибина вимірює, наскільки граф далекий від зірки. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Tree-depth.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.hermann-gruber.com/data/icalp08.pdf http://www.cs.uu.nl/research/techreps/repo/CS-1995/1995-03.pdf |
| dbo:wikiPageID | 25768005 (xsd:integer) |
| dbo:wikiPageLength | 21098 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1098110900 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pursuit-evasion dbr:Minor_(graph_theory) dbr:Degeneracy_(graph_theory) dbc:Graph_minor_theory dbr:Approximation_algorithm dbr:Path_graph dbr:Pathwidth dbr:Pennsylvania_State_University dbr:Cycle_rank dbr:Undirected_graph dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:International_Colloquium_on_Automata,_Languages_and_Programming dbr:International_Symposium_on_Fundamentals_of_Computation_Theory dbr:Robertson–Seymour_theorem dbr:Perfect_binary_tree dbc:Graph_coloring dbc:Graph_invariants dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Connected_graph dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:NP-complete dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Star_(graph_theory) dbr:Clique_(graph_theory) dbr:Halin_graph dbr:Tree_(graph_theory) dbr:Tree_decomposition dbr:Treewidth dbr:Trivially_perfect_graph dbr:Well-quasi-ordering dbr:Trémaux_tree dbr:Dynamic_programming dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Directed_graph dbr:Graph_theory dbr:Journal_of_the_ACM dbr:Regular_language dbr:Higman's_lemma dbr:Pebble_game dbr:Chordal_graph dbr:Bipartite_graph dbr:Star_height dbr:Graph_invariant dbr:Polynomial_time dbr:Forest_(graph_theory) dbr:Series–parallel_graph dbr:Parameterized_complexity dbr:Binary_search dbr:File:Tree-depth.svg |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Citation dbt:Harv dbt:Harvtxt dbt:Nobreak dbt:Reflist dbt:Sfnp dbt:Short_description |
| dct:subject | dbc:Graph_minor_theory dbc:Graph_coloring dbc:Graph_invariants |
| gold:hypernym | dbr:Invariant |
| rdf:type | 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 tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star. (en) В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина графа измеряет, насколько граф далёк от дерева, глубина дерева измеряет, насколько граф далёк от звезды. (ru) У теорії графів деревна глибина зв'язного неорієнтованого графа G — це числовий інваріант G, мінімальна висота дерева Тремо для суперграфа графа G. Цей інваріант і близькі поняття зустрічаються під різними назвами в літературі, зокрема як число ранжування вершин, впорядковане хроматичне число і мінімальна висота виключення дерева. Поняття близьке також до таких понять, як циклічний ранг орієнтованих графів і висота ітерації мови регулярних мов. Інтуїтивно, якщо деревна ширина графа вимірює, наскільки граф далекий від дерева, деревна глибина вимірює, наскільки граф далекий від зірки. (uk) |
| rdfs:label | Глубина дерева (теория графов) (ru) Tree-depth (en) Деревна глибина (теорія графів) (uk) |
| owl:sameAs | freebase:Tree-depth yago-res:Tree-depth wikidata:Tree-depth dbpedia-ru:Tree-depth dbpedia-uk:Tree-depth https://global.dbpedia.org/id/4wkGg |
| prov:wasDerivedFrom | wikipedia-en:Tree-depth?oldid=1098110900&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Tree-depth.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Tree-depth |
| is dbo:wikiPageDisambiguates of | dbr:Depth |
| is dbo:wikiPageRedirects of | dbr:Treedepth |
| is dbo:wikiPageWikiLink of | dbr:Pathwidth dbr:Cycle_rank dbr:Induced_path dbr:Integer_programming dbr:1-planar_graph dbr:Graph_bandwidth dbr:Graph_coloring dbr:Graph_minor dbr:Contraction_hierarchies dbr:Benjamin_Rossman dbr:Chordal_completion dbr:Depth dbr:Treewidth dbr:Well-quasi-ordering dbr:Trémaux_tree dbr:Efficient_approximately-fair_item_allocation dbr:Circuit_rank dbr:Treedepth |
| is foaf:primaryTopic of | wikipedia-en:Tree-depth |
