Частичное k-дерево — это вид графа, либо подграф k-дерева, либо граф с древовидной шириной, не превосходящей k. Много комбинаторных NP-трудных задач на графах решаются за полиномиальное время, если ограничиться частичными k-деревьями c некоторым ограниченным значением k.

Миноры графов

Для любой фиксированной константы k частичные k деревья замкнуты относительно операции взятия миноров графов, а потому по теореме Робертсона – Сеймура, такое семейство графов может быть описано конечным набором запрещённых миноров. Частичные 1-деревья — это в точности леса и их единственным запрещённым минором является треугольник. Для частичных 2-деревьев единственным запрещённым минором является полный граф с четырьмя вершинами. Однако при возрастании значения k далее число запрещённых миноров растёт. Для частичных 3-деревьев имеется четыре запрещённых минора — полный граф с пятью вершинами, октаэдральный граф с шестью вершинами, Граф Вагнера с восемью вершинами и граф пятигольной призмы с десятью вершинами.

Динамическое программирование Много алгоритмических задач, NP-полных для произвольных графов, могут быть эффективно решены для частичных k-деревьев с помощью динамического программирования, если использовать древовидную декомпозицию этих графов.

Связанные семейства графов Если семейство графов имеет древовидную ширину, ограниченную числом k, то оно является подсемейством частичных k-деревьев. Семейства графов с этим свойством включают кактусы, псевдолеса, параллельно-последовательные графы, внешнепланарные графы, графы Халина и графы Аполлония. Например, параллельно-последовательные графы являются подсемейством частичных 2-деревьев. Более строго, граф является частичным 2-деревом тогда и только тогда, когда любой его шарнир является параллельно-последовательным.

Графы потока управления, возникающие при трансляции структурированных программ также имеют ограниченную древовидную ширину, что позволяет некоторые задачи, такие как распределение регистров, выполнять эффективно.

Примечания

Литература

.

. .

Категория:Деревья (графы) Категория:Теория миноров графов