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

В теорії графів деревна декомпозиція — це відображення графа в дерево, яке можна використати для визначення деревної ширини графа і прискорення розв'язання певних обчислювальних задач на графах.

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

В галузі машинного навчання деревна декомпозиція називається деревом зчленувань, деревом клік або деревом суміжності. Деревна декомпозиція відіграє важливу роль у задачах, на зразок імовірнісного логічного виведення^[en], пошуку допустимих значень^[en], оптимізації запитів СУБД і розкладання матриць.

Поняття деревної декомпозиції спочатку запропонував Р. Галін^[en][1]. Пізніше його перевідкрили Н. Робертсон^[en] і П. Сеймур^[ru][2] і відтоді поняття вивчали багато інших авторів^[3].

Визначення

Інтуїтивно деревна декомпозиція подає вершини заданого графа 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].

Див. також

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