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

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

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

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

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

Визначення

Інтуїтивно деревна декомпозиція подає вершини заданого графа 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. Цю властивість можна сформулювати еквівалентно: якщо ${\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}$.

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

Докладніше: Деревна ширина (теорія графів)

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

Ширина деревної декомпозиції — це розмір її найбільшої множини 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 проходом дерева від низу до верху:

${\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 є константою, всі обчислення займають сталий час на одне ребро або вузол. Розмір найбільшої незалежної множини є найбільшим значенням, збереженим у кореневому вузлі, а саму найбільшу незалежну множину можна знайти (що є стандартним для динамічного програмування) шляхом відстеження у зворотному порядку цих збережених значень, починаючи з найбільшого значення. Таким чином, у графах обмеженої деревної ширини задачу пошуку найбільшої незалежної множини можна розв'язати за лінійний час. Подібні алгоритми застосовні для багатьох інших задач на графах.

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

Див. також

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

Примітки

1. Halin, 1976.
2. Robertson, Seymour, 1984.
3. Diestel, 2005, с. 354–355.
4. Diestel, 2005, с. section 12.3.
5. Bodlaender, 1996.
6. Arnborg, Corneil, Proskurowski, 1987.
7. Bertelé, Brioschi, 1972.
8. Arnborg, Proskurowski, 1989; Bern, Lawler, Wong, 1987; Bodlaender, 1988.

Література

• 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. — ..
• 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. — , 2005. — . з джерела 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..