Tree-depth
In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. 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 graph width parameter measures how far a graph is from being a tree, this parameter measures how far a graph is from being a star.
Wikipage redirect
primaryTopic
Tree-depth
In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. 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 graph width parameter measures how far a graph is from being a tree, this parameter measures how far a graph is from being a star.
has abstract
In graph theory, the tree-dept ...... a graph is from being a star.
@en
В теории графов глубина дерева ...... асколько граф далёк от звезды.
@ru
У теорії графів деревна глибин ...... кільки граф далекий від зірки.
@uk
Link from a Wikipage to an external page
Wikipage page ID
25,768,005
page length (characters) of wiki page
Wikipage revision ID
1,016,711,620
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
hypernym
comment
In graph theory, the tree-dept ...... a graph is from being a star.
@en
В теории графов глубина дерева ...... асколько граф далёк от звезды.
@ru
У теорії графів деревна глибин ...... кільки граф далекий від зірки.
@uk
label
Tree-depth
@en
Глубина дерева (теория графов)
@ru
Деревна глибина (теорія графів)
@uk