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

В теорії графів деревна ширина неорієнтованого графу — це число, асоційоване з графом. Деревну ширину можна визначити декількома еквівалентними способами: як розмір найбільшої множини вершин у деревному розкладі, як розмір найбільшої кліки в хордальному доповненні графу, як найбільший порядок укриття під час опису стратегії гри переслідування на графі або як найбільший порядок ожини, набору зв'язних підграфів, які дотикаються один з одним. Деревна ширина часто використовується як параметр в аналізі параметричної складності алгоритмів на графах. Графи з шириною дерева, що не перевищує k, називаються частковими k-деревами. Багато інших добре вивчених сімейств графів також мають обмежену ширину дерева.

Поняття ширини дерева ввів Халін (Halin, 1976) ґрунтуючись на іншому параметрі, числі Хадвігера, з яким деревна ширина має низку спільних властивостей. Пізніше деревну ширину перевідкрили Робертсон і Сеймур, і відтоді її вивчали багато авторів.

Визначення

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

Деревна декомпозиція графу G = (V, E) — дерево T, вершинами X₁, …, X_n якого є підмножини V, які задовольняють таким властивостям:

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

Ширина деревної декомпозиції — це розмір її найбільшої множини X_i мінус одиниця.

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

Так само, деревна ширина G на одиницю менша від розміру найбільшої кліки в хордальному графі з мінімальним кліковим числом, який містить G. Хордальний граф з цим кліковим числом можна отримати, якщо додати в G ребра між будь-якими двома вершинами, якщо обидва належать одній і тій самій (хоча б одній) множини X_i.

Деревну ширину можна також описати в термінах укриттів, функцій, що описують стратегії ухилення для деяких ігор переслідування на графі. Граф G має деревну ширину k в тому і тільки в тому випадку, коли в ньому є укриття порядку k + 1, але немає укриття з більшим порядком. Тут укриття порядку k + 1 — це функція β, яка відображає кожну множина X із максимум k вершинами в G в одну зі зв'язних компонент графу G \ X і для якої виконується властивість монотонності

$\beta (Y)\subseteq \beta (X)$ при $X\subseteq Y$.

Ожина порядку чотири на 3×3 графі-ґратці, існування якої показує, що граф має деревну ширину принаймні  3

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

Приклади

Будь-який повний граф K_n має деревну ширину n − 1. Це легко побачити, якщо використати визначення деревної ширини в термінах хордальних графів — повний граф вже хордальний, і додавання ребер не може зменшити розміру найбільшої кліки.

Зв'язні графи, які мають щонайменше дві вершини, мають деревну ширину 1 тоді й лише тоді, коли це дерево. Дерево має деревну ширину одиниця з тієї ж причини, що й повні графи (а саме, вони хордальні й мають найбільшу кліку розміром два). Навпаки, якщо граф має цикл, то будь-яке хордальне доповнення графу містить щонайменше один трикутник, звідки випливає, що деревна ширина графу не менше двох.

Обмежена деревна ширина

Сімейства графів дерев обмеженої ширини

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

Планарні графи не мають обмеженої деревної ширини, оскільки 'n' × n ґратка — це планарний граф, який має деревну ширину рівно n. Таким чином, якщо F — це сімейство мінорно-замкнутих графів з обмеженою деревною шириною, воно не може включати всіх планарних графів. Навпаки, якщо деякий планарний граф не може бути мінором графів у сімействі F, то існує константа k, така що всі графи в F мають деревну ширину не більшу від k. Таким чином, наступні три умови еквівалентні між собою:

1. F — сімейство мінорно-замкнутих графів обмеженої деревної ширини;
2. Один зі скінченного числа заборонених мінорів для F планарний;
3. F є сімейством мінорно-замкнутих графів, що включає не планарні графи.

Заборонені мінори

Чотири заборонених мінори для деревної ширини 3

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

• Для k = 1 єдиним забороненим мінором є цикл із 3 вершинами.
• Для k = 2 єдиним забороненим мінором є повний граф K₄ з 4 вершинами.
• Для k = 3 існує чотири заборонених мінори — K_5, граф октаедра, граф п'ятикутної призми і граф Вагнера. Два з перелічених поліедральних графів є планарними.

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

Алгоритми

Обчислення ширини дерева

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

На практиці алгоритм Шойхета і Гайгера (Shoikhet, Geiger, 1997) може знайти деревну ширину графів, що мають розмір до 100 вершин і деревну ширину аж до 11, знаходженням хордального доповнення цих графів з оптимальною деревною шириною.

Розв'язання інших задач на графах з малою шириною дерева

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

Наприклад, задачу розфарбовування графу деревної ширини k можна розв'язати за допомогою динамічного програмування на деревному розкладі графу. Для кожної множини X_i деревного розкладу і кожного розбиття вершин X_i на кольори алгоритм визначає, чи припустима отримана розмальовка і чи можна її розширити на всі похідні вершини розкладу шляхом комбінування інформації однакового типу і запам'ятовування в цих вершинах. Результуючий алгоритм знаходить оптимальну розмальовку графу з n вершинами за час O(k^k + O(1)n), що робить цю задачу параметрично складною з фіксованим параметром.

Пов'язані параметри

Шляхова ширина

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

Розмір мінора ґратки

Оскільки деревна ширина ґратки n × n дорівнює n, деревна ширина графу G завжди більша або дорівнює розміру найбільшої квадратної ґратки-мінора графу G. З іншого боку, існує функція f така, що деревна ширина не перевищує f(r), де r — розмір найбільшої квадратної ґратки-мінора. Однак відомі межі f не малі: f повинна бути не менше Ω(r² log r) і не більше 20^2r5. Строгіші кордони відомі для обмежених сімейств графів, що дає ефективні алгоритми для багатьох задач оптимізації на цих сімействах графів за теорією двовимірності. Теорема Халіна про ґратки дає аналог зв'язку між деревною шириною та розміром мінора ґратки для необмежених графів.

Діаметр і локальна деревна ширина

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

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

Число Хадвігера і S-функції

Халін (Halin, 1976) визначає клас параметрів графів, який він називає S-функціями, і цей клас включає деревну ширину. Ці функції мають за область визначення графи, за область значень — цілі числа, і вони повинні набувати значення нуль на графах без ребер і повинні бути монотонними відносно мінорів, тобто збільшуватися на одиницю при додаванні нової вершини, яка суміжна всім попереднім вершинам. Потрібно також, щоб значення функції від графу було рівне більшому зі значень на двох підмножинах, перетин яких є вершинним сепаратором і клікою одночасно. Множина всіх таких функцій утворює повну ґратку відносно операцій поелементної мінімізації й максимізації. Верхній елемент у цій ґратці — деревна ширина, а нижній — число Хадвігера, розмір максимального повного мінора в заданому графі.

Див. також

• Клікова ширина
• Шляхова ширина графу
• Деревна глибина (теорія графів)
• Теорема Курселя

Посилання

• S. Arnborg, D. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree // SIAM Journal on Matrix Analysis and Applications. — 1987. — Т. 8, вип. 2 (4 листопада). — С. 277–284. — DOI:10.1137/0608024..
• Stefan Arnborg, Andrzej Proskurowski, Derek G. Corneil. Forbidden minors characterization of partial 3-trees // Discrete Mathematics. — 1990. — Т. 80, вип. 1 (4 листопада). — С. 1–19. — DOI:10.1016/0012-365X(90)90292-P..
• S. Arnborg, A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Applied Mathematics. — 1989. — Т. 23, вип. 1 (4 листопада). — С. 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 (4 листопада). — С. 216–235. — DOI:10.1016/0196-6774(87)90039-3..
• Umberto Bertelé, Francesco Brioschi. Nonserial Dynamic Programming. — Academic Press, 1972. — 4 листопада. — ISBN 0-12-093450-7..
• Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317 (4 листопада). — С. 105–118. — 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 (4 листопада). — С. 1305–1317. — DOI:10.1137/S0097539793251219..
• Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2 (4 листопада). — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4..
• Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos. Bidimensional parameters and local treewidth // SIAM Journal on Discrete Mathematics. — 2004. — Т. 18, вип. 3 (4 листопада). — С. 501–511. — DOI:10.1137/S0895480103433410..
• Erik D. Demaine, MohammadTaghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited // Algorithmica. — 2024. — Т. 40, вип. 3 (4 листопада). — С. 211–215. — DOI:10.1007/s00453-004-1106-1..
• Erik D. Demaine, MohammadTaghi Hajiaghayi. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — New York : ACM, 2024. — 4 листопада. — С. 840–849..
• Erik D. Demaine, Mohammad Taghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality // Combinatorica. — 2008. — Т. 28, вип. 1 (4 листопада). — С. 19–36. — DOI:10.1007/s00493-008-2140-4. Архівовано з джерела 11 жовтня 2020. Процитовано 1 грудня 2020..
• Reinhard Diestel. A short proof of Halin's grid theorem // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 2004. — Т. 74 (4 листопада). — С. 237–242. — DOI:10.1007/BF02941538..
• Reinhard Diestel. Graph Theory // 3rd. — Springer, 2005. — 4 листопада. — ISBN 3-540-26182-6. Архівовано з джерела 28 липня 2011. Процитовано 1 грудня 2020..
• D. Eppstein. Diameter and treewidth in minor-closed graph families // Algorithmica. — 2000. — Т. 27, вип. 3-4 (4 листопада). — С. 275–291. — DOI:10.1007/s004530010020..
• Markus Frick, Martin Grohe. Deciding first-order properties of locally tree-decomposable structures // Journal of the ACM. — 2001. — Т. 48, вип. 6 (4 листопада). — С. 1184–1206. — DOI:10.1145/504794.504798..
• Alexander Grigoriev, Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge // Algorithmica. — 2007. — Т. 49, вип. 1 (4 листопада). — С. 1–11. — DOI:10.1007/s00453-007-0010-x..
• Rudolf Halin. S-functions for graphs // Journal of Geometry. — 1976. — Т. 8 (4 листопада). — С. 171–186. — DOI:10.1007/BF01917434..
• Jens Lagergren. Graph structure theory (Seattle, WA, 1991). — Providence, RI : American Mathematical Society, 1993. — Т. 147 (4 листопада). — С. 601–621. — DOI:10.1090/conm/147/01202..
• Siddharthan Ramachandramurthi. The structure and number of obstructions to treewidth // SIAM Journal on Discrete Mathematics. — 1997. — Т. 10, вип. 1 (4 листопада). — С. 146–157. — DOI:10.1137/S0895480195280010..
• Neil Robertson, Paul D. Seymour. Graph minors III: Planar tree-width // Journal of Combinatorial Theory, Series B. — 1984. — Т. 36, вип. 1 (4 листопада). — С. 49–64. — DOI:10.1016/0095-8956(84)90013-3..
• Neil Robertson, Paul D. Seymour. Graph minors V: Excluding a planar graph // Journal of Combinatorial Theory, Series B. — 1986. — Т. 41, вип. 1 (4 листопада). — С. 92–114. — DOI:10.1016/0095-8956(86)90030-4..
• Neil Robertson, Paul Seymour, Robin Thomas. Quickly excluding a planar graph // Journal of Combinatorial Theory. — 1994. — Т. 62, вип. 2 (4 листопада). — С. 323–348. — (Series B). — DOI:10.1006/jctb.1994.1073..
• A. Satyanarayana, L. Tung. A characterization of partial 3-trees // Networks. — 1990. — Т. 20, вип. 3 (4 листопада). — С. 299–322. — DOI:10.1002/net.3230200304..
• Paul D. Seymour, Robin Thomas. Graph Searching and a Min-Max Theorem for Tree-Width. // Journal of Combinatorial Theory, Series B. — 1993. — Т. 58, вип. 1 (4 листопада). — С. 22–33. — DOI:10.1006/jctb.1993.1027..
• Kirill Shoikhet, Dan Geiger. Proc. AAAI '97. — 1997. — 4 листопада. — С. 185–190. Архівовано з джерела 2 лютого 2021. Процитовано 1 грудня 2020..
• Mikkel Thorup. All structured programs have small tree width and good register allocation // Information and Computation. — 1998. — Т. 142, вип. 2 (4 листопада). — С. 159–181. — DOI:10.1006/inco.1997.2697..