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

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

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

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

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

Визначення

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

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

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. Цю властивість можна сформулювати еквівалентно: якщо $X_{i}$, $X_{j}$ і $X_{k}$ є вузлами, а $X_{k}$ перебуває на шляху з $X_{i}$ в $X_{j}$, то $X_{i}\cap X_{j}\subseteq X_{k}$.

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

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

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

Деревна ширина

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

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

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

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

На початку 1970-х було помічено, що задачі з великого класу комбінаторних оптимізаційних задач на графах можна ефективно розв'язати за допомогою несеріального динамічного програмування, якщо граф має обмежену розмірність, пов'язаний з деревною шириною параметр. Пізніше, до кінця 1980-х, деякі автори незалежно виявили, що багато алгоритмічних 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 проходом дерева від низу до верху:

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

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

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

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

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

Див. також

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

Література

• S. Arnborg, D. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree // SIAM Journal on Matrix Analysis and Applications. — 1987. — Т. 8, вип. 2. — С. 277–284. — DOI:10.1137/0608024..
• S. Arnborg, A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Applied Mathematics. — 1989. — Т. 23, вип. 1. — С. 11–24. — DOI:10.1016/0166-218X(89)90031-0..
• M. W. Bern, E. L. Lawler, A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs // Journal of Algorithms. — 1987. — Т. 8, вип. 2. — С. 216–235. — DOI:10.1016/0196-6774(87)90039-3..
• Umberto Bertelé, Francesco Brioschi. Nonserial Dynamic Programming. — Academic Press, 1972. — ISBN 0-12-093450-7..
• Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317. — С. 105–118. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-19488-6_110..
• Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth // SIAM Journal on Computing. — 1996. — Т. 25, вип. 6. — С. 1305–1317. — DOI:10.1137/S0097539793251219..
• Reinhard Diestel. [1] — 3rd. — Springer, 2005. — ISBN 3-540-26182-6. Архівовано з джерела 28 липня 2011.
• Rudolf Halin. S-functions for graphs // Journal of Geometry. — 1976. — Т. 8. — С. 171–186. — DOI:10.1007/BF01917434..
• Neil Robertson, Paul D. Seymour. Graph minors III: Planar tree-width // Journal of Combinatorial Theory, Series B. — 1984. — Т. 36, вип. 1. — С. 49–64. — DOI:10.1016/0095-8956(84)90013-3..