About: Tree-depth

An Entity of Type: Abstraction100002137, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org:8891

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
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 25768005 (xsd:integer)
dbo:wikiPageLength
  • 21098 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1098110900 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
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
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License