Часткове k-дерево — це вид графа, який визначають, як підграф k-дерева або граф з деревною шириною, що не перевищує k. Багато комбінаторних NP-складних задач на графах розв'язуються за поліноміальний час, якщо обмежитися частковими k-деревами з деяким обмеженим значенням k.

Мінори графів
 Заборонені мінори для часткових 3-дерев
Для будь-якої фіксованої константи k часткові k дерева замкнуті щодо операції взяття мінорів графів, тому за теоремою Робертсона — Сеймура, таке сімейство графів можна описати скінченним набором заборонених мінорів. Часткові 1-дерева — це точно ліси і їх єдиним забороненим мінором є трикутник. Для часткових 2-дерев єдиним забороненим мінором є повний граф з чотирма вершинами. Однак при зростанні значення k далі кількість заборонених мінорів зростає. Для часткових 3-дерев є чотири заборонені мінори — повний граф з п'ятьма вершинами, октаедральний граф із шістьма вершинами, граф Вагнера з вісьмома вершинами і граф п'ятикутної призми з десятьма вершинами.

Динамічне програмування

Багато алгоритмічних задач, NP-повних для довільних графів, можна ефективно розв'язати для часткових k-дерев за допомогою динамічного програмування, якщо використовувати деревну декомпозицію цих графів.

Пов'язані сімейства графів
Якщо сімейство графів має деревну ширину, обмежену числом k, воно є підсімейством часткових k-дерев. Сімейства графів із цією властивістю включають кактуси, псевдоліси, паралельно-послідовні графи, зовніпланарні графи, графи Халіна та графи Аполлонія. Наприклад, паралельно-послідовні графи є підсімейством часткових 2-дерев. Строгіше, граф є частковим 2-деревом тоді й лише тоді, коли будь-який його шарнір є паралельно-послідовним.

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

Примітки


Література

* 
* .
* 
* .
* .


