Деревна декомпозиція

Інтуїтивно деревна декомпозиція подає вершини заданого графу G як піддерева дерева таким чином, що вершини графу суміжні тільки тоді, коли відповідні піддерева перетинаються. Тоді G утворює підграф графу перетинів піддерев. Повний граф перетинів — це хордальний граф.

Кожне дерево пов'язує вершину графу з множиною вузлів дерева. Щоб визначити це формально, ми подамо кожний вузол дерева як множину вершин, пов'язаних з нею. Тоді для заданого графу G = (V, E) деревна декомпозиція — це пара (X, T), де X = {X₁, …, X_n} є сімейством підмножин множини V, а T є деревом, вузлами якого служать підмножини X_i, які задовольняють таким властивостям: [4]

1. Об'єднання всіх множин X_i дорівнює V. Таким чином, будь-яка вершина графу пов'язана хоча б з одним вузлом дерева.
2. Для будь-якого ребра (v, w) графу існує підмножина X_i, що містить як v, так і w. Таким чином, вершини суміжні в графі, тільки якщо вони відповідають піддеревам, що мають спільний вузол.
3. Якщо X_i і X_j містять вершину v, то всі вузли X_k дерева в (унікальному) шляху між X_i і X_j містять v теж. Тобто вузли, пов'язані з вершиною v, утворюють зв'язну підмножину в T. Цю властивість можна сформулювати еквівалентно: якщо ${\displaystyle X_{i}}$, ${\displaystyle X_{j}}$ і ${\displaystyle X_{k}}$ є вузлами, а ${\displaystyle X_{k}}$ перебуває на шляху з ${\displaystyle X_{i}}$ в ${\displaystyle X_{j}}$, то ${\displaystyle X_{i}\cap X_{j}\subseteq X_{k}}$.

Деревна декомпозиція графу зовсім не унікальна. Наприклад, тривіальна деревна декомпозиція містить всі вершини графу в кореневому вузлі.

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

Деревна декомпозиція (X, T = (I, F)) з деревною шириною k є гладкою, якщо для всіх ${\displaystyle i\in I:|X_{i}|=k+1}$ і для всіх ${\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}$[5].

Дві різні деревні декомпозиції одного графу

Ширина деревної декомпозиції — це розмір її найбільшої множини X_i без одиниці. Деревна ширина tw(G) графу G — це мінімальна ширина серед усіх можливих декомпозицій графу G. У цьому визначенні розмір найбільшої множини зменшено на одиницю з метою зробити деревну ширину дерева рівною одиниці. Деревну ширину можна визначити виходячи з інших структур, а не з деревної декомпозиції. Для цього можна використати хордальні графи, ожини та укриття.

Визначення, чи не перевищує деревна ширина заданого графу G величини k, є NP-повною задачею [6]. Однак, якщо k є фіксованою константою, граф з деревною шириною k можна розпізнати і деревну декомпозицію ширини k можна побудувати за лінійний час[5]. Час роботи цього алгоритму залежить від k експоненціально.

На початку 1970-х було помічено, що задачі з великого класу комбінаторних оптимізаційних задач на графах можна ефективно розв'язати за допомогою несеріального динамічного програмування, якщо граф має обмежену розмірність[7], пов'язаний з деревною шириною параметр. Пізніше, до кінця 1980-х, деякі автори незалежно виявили[8], що багато алгоритмічних NP-повних задач для довільних графів можна ефективно розв'язати за допомогою динамічного програмування для графів з обмеженою деревною шириною за використання деревної декомпозиції цих графів.

Як приклад розглянемо задачу пошуку найбільшої незалежної множини на графі з деревною шириною k. Для розв'язання спочатку виберемо один вузол деревного розкладу як корінь (довільним чином). Для вузла X_i деревної декомпозиції нехай D_i буде об'єднанням множин X_j, успадкованих від X_i. Для незалежної множини S ⊂ X_i нехай A (S, i) означає розмір найбільшої незалежної підмножини I в D_i, такої, що I ∩ X _i = S. Так само для суміжної пари вузлів X_i і X_j з X_i більш віддаленим від кореня, порівняно з X_j, і незалежної множини S ⊂ X _i ∩ X_j нехай B (S, i,j) означає розмір найбільшої незалежної підмножини I в D_i, такої, що I ∩ X _i ∩ X _j = S. Ми можемо обчислити ці значення A і B проходом дерева від низу до верху:

${\displaystyle A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)}$

${\displaystyle B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)}$

де сума у формулі для${\displaystyle A(S,i)}$ береться за нащадками вузла${\displaystyle X_{i}}$ .

У кожному вузлі або ребрі є не більше 2^k множин S, для яких необхідно обчислити ці значення, так що у випадку, коли k є константою, всі обчислення займають сталий час на одне ребро або вузол. Розмір найбільшої незалежної множини є найбільшим значенням, збереженим у кореневому вузлі, а саму найбільшу незалежну множину можна знайти (що є стандартним для динамічного програмування) шляхом відстеження у зворотному порядку цих збережених значень, починаючи з найбільшого значення. Таким чином, у графах обмеженої деревної ширини задачу пошуку найбільшої незалежної множини можна розв'язати за лінійний час. Подібні алгоритми застосовні для багатьох інших задач на графах.

Такий підхід з динамічним програмуванням застосовується в галузі машинного навчання за допомогою алгоритму дерева зчленувань для поширення довіри на графах обмеженої деревної ширини. Підхід також грає ключову роль в алгоритмах обчислення деревної ширини та побудови деревної декомпозиції. Як правило, такі алгоритми мають перший крок, на якому апроксимується деревна ширина і будується деревна декомпозиція з цієї наближеною шириною, а на другому кроці використовується динамічне програмування на отриманому деревному розкладі з метою обчислення точного значення деревної ширини[5].

• Ожина й укриття, два види структур, які можна використовувати як альтернативу деревній декомпозиції для визначення деревної ширини графу
• Декомпозиція графу на гілки, тісно пов'язана структура, ширина якої лінійно пов'язана з деревною шириною
• Метод декомпозиції.
• Шляхова ширина графу