Частичное k-дерево

Запрещённые миноры для частичных 3-деревьев

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

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

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

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