В теории графов «разложение дерева» — это отображение графа (теория графов)|графа в дерево (теория графов)|дерево, которое можно использовать для определения ширины дерева графа и вычисления определенные проблемы ускорились до Грпаэна.
== Определение ==
Интуиция разложения дерева заключается в том, что узлы данного графа 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)
Декомпозиция дерева (теория графов) ⇐ Васина Википедия
-
Автор темыwiki_de
- Всего сообщений: 42916
- Зарегистрирован: 13.01.2023
-
- Похожие темы
- Ответы
- Просмотры
- Последнее сообщение