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

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

Визначення

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

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

Інше визначення таке:

• ${\displaystyle 1}$ якщо |G|=1
• ${\displaystyle 1+\min _{v\in V}td(G-v)}$, якщо G зв'язний і |G|>1
• ${\displaystyle \max _{i}td(G_{i})}$ в іншому випадку, де V — множина вершин графа G і ${\displaystyle G_{i}}$ — зв'язні компоненти G. Це визначення віддзеркалює визначення циклічного рангу орієнтованих графів, яке використовує строгу зв'язність і строго пов'язані компоненти замість неорієнтованої зв'язності і зв'язних компонент.

Деревну глибину можна визначити з використанням розфарбовування графів. Центроване розфарбування графа — це розфарбування вершин, яка має властивість, що в будь-якому зв'язному породженому підграфі є колір, який зустрічається рівно один раз. Тоді деревна глибина — це найменше число кольорів, необхідних для центрованого розфарбовування графа. Якщо F — ліс з висотою d, який має властивість, що кожне ребро графа G з'єднує предка і нащадка в дереві, то можна отримати центроване розфарбування графа G d кольорами розфарбувавши кожну вершину в колір з номером, рівним відстані від кореня у графі F^[7].

Нарешті, можна визначити його в термінах ^[en]. А саме, точно як гру переслідування-ухилення. Уявімо таку гру на неорієнтованому графі. Є два гравці, грабіжник і поліцейський. Грабіжник має одну фішку, яку він рухає вздовж ребер графа. Поліцейський має необмежену кількість фішок, але він хоче мінімізувати кількість використаних фішок. Поліцейський не може пересувати своїх фішок, поміщених на граф. Гра відбувається так. Грабіжник розміщує свою фішку, потім поліцейський повідомляє, куди він хоче поставити наступну фішку і грабіжник після цього може пересунути свою фішку вздовж ребер, але не через зайняті вершини. Гра завершується, коли поліцейський поміщає наступну фішку поверх фішки грабіжника. Деревна глибина даного графа визначає найменше число фішок, необхідних для гарантованого виграшу. Для зірки достатньо двох фішок — розміщуємо першу фішку в центрі зірки, змушуючи грабіжника перейти в якийсь промінь, а потім поміщаємо другу фішку на фішку грабіжника. Для шляху з ${\displaystyle n}$ вершинами поліцейський використовує стратегію двійкового пошуку, яка гарантує використання не більше ${\displaystyle \lceil \log _{2}(n+1)\rceil }$ фішок.

Приклади

Деревна глибина повного графа K₄ і повного двочасткового графа K_3,3 дорівнює чотирьом, тоді як деревна глибина шляху P₇ дорівнює трьом.

Деревна глибина повного графа дорівнює кількості його вершин, і в цьому випадку єдиним можливим лісом F, для якого будь-яка пара вершин перебуває у відношенні предок-нащадок, є одиничний шлях. Схожим чином деревна глибина повного двочасткового графа K_x,y дорівнює min(x,y) + 1, і як би ми не розташовували вершини, листки лісу F повинні мати принаймні min(x,y) предків F. Ліс, на якому досягається min(x,y) + 1, можна побудувати, утворивши шлях з вершин меншої за розміром частки графа, а вершини більшої частки формують листки дерева F, сполучені з нижньою вершиною шляху.

Деревна глибина шляху з n вершинами дорівнює рівно ${\displaystyle \lceil \log _{2}(n+1)\rceil }$. Ліс F, що подає цей шлях з такою глибиною, можна утворити, помістивши корінь у середню точку шляху F і продовжуючи рекурсію в двох менших шляхах з обох боків від кореня.

Деревна глибина і зв'язок з деревною шириною

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

Будь-який ліс із n вершинами має деревну глибину O(log n). Для лісу можна завжди знайти стале число вершин, видалення яких дає ліс, який можна розділити на два менших підліси з максимум 2n/3 вершин у кожному. Рекурсивно ділячи ці два підліси, легко можна досягти логарифмічної верхньої межі деревної глибини. Та ж техніка, застосована до деревної декомпозиції графа, показує, що, якщо деревна ширина n-вершинного графа G дорівнює t, тоді деревна глибина графа G дорівнює O(t log n). Оскільки зовніпланарні графи, паралельно-послідовні графи і графи Халіна мають обмежену деревну ширину, вони всі теж мають максимум логарифмічну деревну глибину.

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

Мінори графа

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

Якщо C — клас графів, замкнутих відносно утворення мінорів, то графи C мають деревну глибину ${\displaystyle O(1)}$ тоді й лише тоді, коли C не включає всіх шляхів.

Породжені підграфи

Деревна глибина має тісний зв'язок з теорією породжених підграфів графа. В класі графів, що мають деревну глибину не більше d (для будь-якого фіксованого натурального d), властивість бути породженим підграфом є ^[en]. Основна ідея доведення, що цей зв'язок цілком квазівпорядкований, полягає у використанні індукції за d. Ліси висоти d можна інтерпретувати як послідовність лісів висоти d − 1 (утворених видаленням коренів дерев висоти d) і можна використовувати ^[en], щоб показати, що ці послідовності цілком квазівпорядковані.

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

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

Складність

Визначення глибини дерева є складною обчислювальною задачею — відповідна задача розпізнавання NP-повна. Завдання залишається NP-повною для двочасткових графів, як і для хордальних графів.

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

Бодлендер, Гілберт, Хафстейнссон і Клокс запропонували апроксимаційний алгоритм пошуку деревної глибини з апроксимаційним коефіцієнтом ${\displaystyle O((\log n)^{2})}$. Алгоритм заснований на факті, що деревна глибина логарифмічно залежить від деревної ширини графа.

Оскільки деревна глибина монотонна за мінорами графа, задача її пошуку ^[en] — існує алгоритм обчислення деревної глибини, що працює за час ${\displaystyle f(d)n^{O(1)}}$, де d — глибина даного графа і n — число вершин. Таким чином, для будь-якого фіксованого значення d задача перевірки, чи не перевершує деревна глибина значення d, може бути розв'язана за поліноміальний час. Конкретніше — залежність від n у цьому алгоритмі можна зробити лінійною таким чином: будуємо дерево пошуку в глибину і перевіряємо, перевищує глибина дерева величину 2^d чи ні. Якщо перевищує, то глибина дерева більша від d і задачу роз'язано. Якщо ні, можна скористатись побудовою дерева пошуку на невелику глибину для декомпозиції дерева і стандартною технікою динамічного програмування для графів з обмеженою деревною шириною, щоб обчислити глибину за лінійний час. Більш складний алгоритм розв'язування за лінійний час, заснований на планарності мінорів, що виключаються під час пошуку в глибину, запропонували раніше Бодлендер, Деоган, Дженсен та Клокс. Покращений параметричний алгоритм див. у Райдля, Россманіта, Вілламіла і Сікдара.

Можна обчислити глибину дерева точно для графів, значення глибини для яких може бути великим, за час O(cⁿ) з константою c, трохи меншою від 2.

Примітки

1. Bodlaender et al, 1998.
2. Rossman, 2008.
3. Nešetřil, Ossona de Mendez, 2012, с. 116.
4. Nešetřil, Ossona de Mendez, 2012, с. 115, Definition 6.1.
5. David Eppstein. Graph parameters and cliques in supergraphs. — . з джерела 9 січня 2014..
6. Nešetřil, Ossona de Mendez, 2012, с. 117,Lemma 6.1.
7. Nešetřil, Ossona de Mendez, 2012, с. 125–128, Section 6.5, "Centered Colorings".
8. Gruber, Holzer, 2008, с. Theorem 5.
9. Hunter, 2011 та Main Theorem.
10. Nešetřil, Ossona de Mendez, 2012, с. 117, Formula 6.2.
11. Bodlaender et al, 1995.
12. Nešetřil, Ossona de Mendez, 2012, с. 124, Corollary 6.1.
13. Nešetřil, Ossona de Mendez, 2012, с. 123.
14. Nešetřil, Ossona de Mendez, 2012, с. 117,Lemma 6.2.
15. Nešetřil, Ossona de Mendez, 2012, с. 122, Proposition 6.4.
16. Nešetřil, Ossona de Mendez, 2012, с. 137, Lemma 6.13.
17. Nešetřil, Ossona de Mendez, 2012, с. 138. Figure 6.6 on p. 139.
18. Pothen, 1988.
19. Dereniowski, Nadolski, 2006.
20. Aspvall, Heggernes, 1994.
21. Deogun et al, 1999.
22. Iyer et al, 1988.
23. Schäffer, 1989.
24. Nešetřil, Ossona de Mendez, 2012, с. 138.
25. Reidl et al, 2014.
26. Fomin et al, 2013.

Література

• Bengt Aspvall, Pinar Heggernes. Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time // BIT. — 1994. — Т. 34, вип. 4 (17 червня). — С. 484–509. — DOI:10.1007/BF01934264..
• Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, Zsolt Tuza. Rankings of graphs // SIAM Journal on Discrete Mathematics. — 1998. — Т. 11, вип. 1 (17 червня). — С. 168–181. — DOI:10.1137/S0895480195282550.^{[недоступне посилання з Июнь 2018]}.
• Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree // Journal of Algorithms. — 1995. — Т. 18, вип. 2 (17 червня). — С. 238–255. — DOI:10.1006/jagm.1995.1009. — (CiteSeerX): 10.1.1.29.7198..
• Jitender S. Deogun, Ton Kloks, Dieter Kratsch, Haiko Müller. On the vertex ranking problem for trapezoid, circular-arc and other graphs // Discrete Applied Mathematics. — 1999. — Т. 98 (17 червня). — С. 39–34. — DOI:10.1016/S0166-218X(99)00179-1..
• D. Dereniowski, A. Nadolski. Vertex rankings of chordal graphs and weighted trees // . — 2006. — Т. 98 (17 червня). — С. 96–100. — DOI:10.1016/j.ipl.2005.12.006..
• Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk. Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers / Gregory Gutin, Stefan Szeider. — 2013. — Т. 8246. — С. 137–149. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-03898-8_13..
• Hermann Gruber, Markus Holzer. [1] — Springer-Verlag, 2008. — Т. 5126. — С. 39–50. — (Lecture Notes on Computer Science) — DOI:10.1007/978-3-540-70583-3_4. з джерела 11 липня 2011.
• Paul Hunter. 18th . — Springer-Verlag, 2011. — Т. 6914. — С. 217–228. — (Lecture Notes on Computer Science) — DOI:10.1007/978-3-642-22953-4_19.
• Ananth V. Iyer, H. Donald Ratliff, Gopalakrishnan Vijayan. Optimal node ranking of trees // . — 1988. — Т. 28 (17 червня). — С. 225–201. — DOI:10.1016/0020-0190(88)90194-9..
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Heidelberg : Springer, 2012. — Т. 28. — С. 115–144. — (Algorithms and Combinatorics) — . — DOI:10.1007/978-3-642-27875-4..
• Alex Pothen. The complexity of optimal elimination trees. — Pennsylvania State University, 1988. — (Tech. Report CS-88-13).
• Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar.  / Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias. — 2014. — Т. 8572. — С. 931–942. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-662-43948-7_77..
• Benjamin Rossman. Homomorphism preservation theorems // . — 2008. — Т. 55, вип. 3 (17 червня). — С. Article 15. — DOI:10.1145/1379759.1379763..
• Alejandro A. Schäffer. Optimal node ranking of trees in linear time // . — 1989. — Т. 33 (17 червня). — С. 91–19. — DOI:10.1016/0020-0190(89)90161-0..