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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Визначення[ред. | ред. код]

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

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

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

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

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

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

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

при .

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

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

Приклади[ред. | ред. код]

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

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

Обмежена деревна ширина[ред. | ред. код]

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

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

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

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

Заборонені мінори[ред. | ред. код]

Докладніше: Характеризація забороненими графами
Чотири заборонених мінори для деревної ширини 3

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

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

Алгоритми[ред. | ред. код]

Обчислення ширини дерева[ред. | ред. код]

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

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

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

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

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

Пов'язані параметри[ред. | ред. код]

Шляхова ширина[ред. | ред. код]

Докладніше: Шляхова ширина графу

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

Розмір мінора ґратки[ред. | ред. код]

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

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

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

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

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

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. ↑ (Robertson, Seymour, 1984)
  2. ↑ (Diestel, 2005) стр.354–355
  3. ↑ (Diestel, 2005), секция 12.3
  4. ↑ Seymour, Thomas, 1993.
  5. ↑ а б (Bodlaender, 1998)
  6. ↑ Thorup, 1998.
  7. ↑ Robertson, Seymour, 1986.
  8. ↑ (Bodlaender, 1988).
  9. ↑ (Arnborg, Proskurowski, Corneil, 1990); (Satyanarayana, Tung, 1990).
  10. ↑ Ramachandramurthi, 1997.
  11. ↑ Lagergren, 1993.
  12. ↑ Arnborg, Corneil, Proskurowski, 1987.
  13. ↑ (Bodlaender, 1996).
  14. ↑ Bertelé, Brioschi, 1972.
  15. ↑ (Arnborg, Proskurowski, 1989); (Bern, Lawler, Wong, 1987); (Bodlaender, 1988).
  16. ↑ (Robertson, Seymour, Thomas, 1994). Об Ω в нижней оценке смотрите «O» большое и «o» малое.
  17. ↑ а б Demaine, Hajiaghayi, 2008.
  18. ↑ Diestel, 2004.
  19. ↑ Eppstein, 2000.
  20. ↑ (Eppstein, 2000); (Demaine, Hajiaghayi, 2004a).
  21. ↑ Demaine, Hajiaghayi, 2004b.
  22. ↑ (Demaine, Fomin, Hajiaghayi, Thilikos, 2004); (Demaine, Hajiaghayi, 2008).
  23. ↑ Frick, Grohe, 2001.
  24. ↑ Grigoriev, Bodlaender, 2007.

Посилання[ред. | ред. код]

  • S. Arnborg, D. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree // SIAM Journal on Matrix Analysis and Applications. — 1987. — Т. 8, вип. 2 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 216–235. — DOI:10.1016/0196-6774(87)90039-3..
  • Umberto Bertelé, Francesco Brioschi. Nonserial Dynamic Programming. — Academic Press, 1972. — 21 квітня. — ISBN 0-12-093450-7..
  • Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 501–511. — DOI:10.1137/S0895480103433410..
  • Erik D. Demaine, MohammadTaghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited // Algorithmica. — 2024. — Т. 40, вип. 3 (21 квітня). — С. 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. — 21 квітня. — С. 840–849..
  • Erik D. Demaine, Mohammad Taghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality // Combinatorica. — 2008. — Т. 28, вип. 1 (21 квітня). — С. 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 (21 квітня). — С. 237–242. — DOI:10.1007/BF02941538..
  • Reinhard Diestel. Graph Theory // 3rd. — Springer, 2005. — 21 квітня. — ISBN 3-540-26182-6. Архівовано з джерела 28 липня 2011. Процитовано 1 грудня 2020..
  • D. Eppstein. Diameter and treewidth in minor-closed graph families // Algorithmica. — 2000. — Т. 27, вип. 3-4 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 1–11. — DOI:10.1007/s00453-007-0010-x..
  • Rudolf Halin. S-functions for graphs // Journal of Geometry. — 1976. — Т. 8 (21 квітня). — С. 171–186. — DOI:10.1007/BF01917434..
  • Jens Lagergren. Graph structure theory (Seattle, WA, 1991). — Providence, RI : American Mathematical Society, 1993. — Т. 147 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 323–348. — (Series B). — DOI:10.1006/jctb.1994.1073..
  • A. Satyanarayana, L. Tung. A characterization of partial 3-trees // Networks. — 1990. — Т. 20, вип. 3 (21 квітня). — С. 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 (21 квітня). — С. 22–33. — DOI:10.1006/jctb.1993.1027..
  • Kirill Shoikhet, Dan Geiger. Proc. AAAI '97. — 1997. — 21 квітня. — С. 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 (21 квітня). — С. 159–181. — DOI:10.1006/inco.1997.2697..
Отримано з https://uk.wikipedia.org/w/index.php?title=Деревна_ширина_(теорія_графів)&oldid=37552505