Оглавление
Древовидная декомпозиция
-
Определение древовидной декомпозиции
- Древовидная декомпозиция преобразует граф в дерево, где вершины графа связаны с узлами дерева.
- Вершины смежны только тогда, когда соответствующие поддеревья пересекаются.
- Граф полного пересечения является хордовым графом.
-
Свойства древовидной декомпозиции
- Объединение всех множеств вершин равно множеству вершин графа.
- Для каждого ребра графа существует подмножество, содержащее обе вершины.
- Узлы, связанные с вершиной, образуют связное подмножество дерева.
-
Ширина дерева
- Ширина древовидной декомпозиции равна размеру наибольшего набора вершин минус единица.
- Древовидная ширина графа – это минимальная ширина среди всех возможных древовидных разложений.
-
Динамическое программирование
- Задачи комбинаторной оптимизации могут быть эффективно решены с помощью динамического программирования для графов ограниченной ширины дерева.
- Пример: задача нахождения максимального независимого множества решается за линейное время.
-
Альтернативные структуры
- Заросли ежевики и убежища могут использоваться для определения древовидной ширины графа.
- Ветвление-декомпозиция имеет ширину в пределах постоянного коэффициента ширины дерева.
-
Метод декомпозиции
- Древовидная декомпозиция используется в методе декомпозиции для решения задачи удовлетворения ограничений.