Декомпозиция дерева (теория графов) ⇐ Васина Википедия

[wiki_de]

В теории графов «разложение дерева» — это отображение графа (теория графов)|графа в дерево (теория графов)|дерево, которое можно использовать для определения ширины дерева графа и вычисления определенные проблемы ускорились до Грпаэна.

== Определение ==
Интуиция разложения дерева заключается в том, что узлы данного графа G представлены как поддерево разложения дерева таким образом, что узлы в G находятся рядом друг с другом тогда и только тогда, когда их поддеревья перекрываются. Это означает, что G образует подграф графа пересечений поддеревьев. Полный граф пересечений является хордальным графом.

== Формальное определение ==
«Древовидное разложение» G = (V,E) представляет собой пару (X,T), где T = (I,F)< / math> — дерево, а X = \{X_i~|~i \in I\ — семейство (математика)|семейство подмножеств узлов (теория графов)|множество узлов V графика, так что:

* \bigcup_{i \in I} X_i = V.
* Для всех ребер (теория графов)|ребер (v,w) \in E существует i \in I с v,w \in X_i< /математика>.
* Для всех i,j,k \in I применяется следующее: если j находится на пути от i до k< /math> в T, затем X_i \cap X_k \subseteq X_j.

== Литература ==

* * *

Категория:Основные понятия (теория графов)
Категория:Деревья и леса
Категория:Теория графов

Подробнее: https://de.wikipedia.org/wiki/Baumzerle ... entheorie)