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

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

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

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

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

Визначення

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

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

  1. Об'єднання всіх множин Xi дорівнює V. Таким чином, будь-яка вершина графу пов'язана хоча б з одним вузлом дерева.
  2. Для будь-якого ребра (v, w) графу існує підмножина Xi, що містить як v, так і w. Таким чином, вершини суміжні в графі, тільки якщо вони відповідають піддеревам, що мають спільний вузол.
  3. Якщо Xi і Xj містять вершину v, то всі вузли Xk дерева в (унікальному) шляху між Xi і Xj містять v теж. Тобто вузли, пов'язані з вершиною v, утворюють зв'язну підмножину в T. Цю властивість можна сформулювати еквівалентно: якщо , і є вузлами, а перебуває на шляху з в , то .

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

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

Деревна декомпозиція (X, T = (I, F)) з деревною шириною k є гладкою, якщо для всіх і для всіх [5].

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

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

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

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

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

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

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

де сума у формулі для береться за нащадками вузла .

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

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

Див. також

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


Примітки

Література

  • S. Arnborg, D. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree // SIAM Journal on Matrix Analysis and Applications.  1987. Т. 8, вип. 2 (3 листопада). С. 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 (3 листопада). С. 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 (3 листопада). С. 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 (3 листопада). С. 1305–1317. DOI:10.1137/S0097539793251219..
  • Reinhard Diestel. Graph Theory. — 3rd. Springer, 2005. — ISBN 3-540-26182-6..
  • Rudolf Halin. S-functions for graphs // Journal of Geometry.  1976. Т. 8 (3 листопада). С. 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 (3 листопада). С. 49–64. DOI:10.1016/0095-8956(84)90013-3..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.