Tree-depth
http://dbpedia.org/resource/Tree-depth an entity of type: Abstraction100002137
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.
rdf:langString
В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина графа измеряет, насколько граф далёк от дерева, глубина дерева измеряет, насколько граф далёк от звезды.
rdf:langString
У теорії графів деревна глибина зв'язного неорієнтованого графа G — це числовий інваріант G, мінімальна висота дерева Тремо для суперграфа графа G. Цей інваріант і близькі поняття зустрічаються під різними назвами в літературі, зокрема як число ранжування вершин, впорядковане хроматичне число і мінімальна висота виключення дерева. Поняття близьке також до таких понять, як циклічний ранг орієнтованих графів і висота ітерації мови регулярних мов. Інтуїтивно, якщо деревна ширина графа вимірює, наскільки граф далекий від дерева, деревна глибина вимірює, наскільки граф далекий від зірки.
rdf:langString
rdf:langString
Глубина дерева (теория графов)
rdf:langString
Tree-depth
rdf:langString
Деревна глибина (теорія графів)
xsd:integer
25768005
xsd:integer
1098110900
rdf:langString
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.
rdf:langString
В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина графа измеряет, насколько граф далёк от дерева, глубина дерева измеряет, насколько граф далёк от звезды.
rdf:langString
У теорії графів деревна глибина зв'язного неорієнтованого графа G — це числовий інваріант G, мінімальна висота дерева Тремо для суперграфа графа G. Цей інваріант і близькі поняття зустрічаються під різними назвами в літературі, зокрема як число ранжування вершин, впорядковане хроматичне число і мінімальна висота виключення дерева. Поняття близьке також до таких понять, як циклічний ранг орієнтованих графів і висота ітерації мови регулярних мов. Інтуїтивно, якщо деревна ширина графа вимірює, наскільки граф далекий від дерева, деревна глибина вимірює, наскільки граф далекий від зірки.
xsd:nonNegativeInteger
21098
