Перегляд вихідного коду сторінки Деревна глибина (теорія графів)

У [[Теорія графів|теорії графів]] '''деревна глибина''' [[Зв'язний граф|зв'язного]] [[Граф (математика)|неорієнтованого графа]] ''G''&nbsp;— це числовий [[Інваріант графа|інваріант]] ''G'', мінімальна висота [[Дерево Тремо|дерева Тремо]] для [[Словник термінів теорії графів|суперграфа]] графа ''G''. Цей інваріант і близькі поняття зустрічаються під різними назвами в літературі, зокрема як число ранжування вершин, впорядковане хроматичне число і мінімальна висота виключення дерева. Поняття близьке також до таких понять, як [[циклічний ранг]] [[Орієнтований граф|орієнтованих графів]] і [[висота ітерації мови]] [[Регулярна мова|регулярних мов]]{{Sfn|Bodlaender et al|1998}}{{Sfn|Rossman|2008}}{{Sfn|Nešetřil, Ossona de Mendez|2012|с=116}}. Інтуїтивно, якщо [[Деревна ширина (теорія графів)|деревна ширина]] графа вимірює, наскільки граф далекий від дерева, деревна глибина вимірює, наскільки граф далекий від зірки.

== Визначення ==
Деревну глибину графа ''G'' можна визначити як мінімальну висоту [[Дерево (теорія графів)|лісу]] ''F'' із властивістю, що будь-яке ребро графа ''G'' з'єднує пару вершин, пов'язаних відношенням предок-нащадок у ''F''{{Sfn|Nešetřil, Ossona de Mendez|2012|с=115, Definition 6.1}}. Якщо ''G'' зв'язний, цей ліс має бути єдиним деревом. Ліс не обов'язково має бути підграфом графа ''G'', але якщо є, то це [[дерево Тремо]] для ''G''.

Множина пар предок-нащадок у ''F'' утворює [[тривіально досконалий граф]], і висота ''F'' є розміром найбільшої [[Кліка (теорія графів)|кліки]] цього графа. Таким чином, деревну глибину альтернативно можна визначити як розмір найбільшої кліки в тривіально досконалому суперграфі графа ''G'', що є дзеркальним відбиттям [[Деревна ширина (теорія графів)|деревної ширини]], яка на одиницю менша від розміру найбільшої кліки в [[Хордальний граф|хордальному]] суперграфі графа ''G''<ref>{{Стаття|author=David Eppstein|url=http://11011110.livejournal.com/258705.html|title=Graph parameters and cliques in supergraphs|date=2012 (November 15)|archiveurl=https://web.archive.org/web/20140109203630/http://11011110.livejournal.com/258705.html|archivedate=2014-01-09}}.</ref>.

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

* <math>1</math> якщо |''G''|=1
* <math>1+\min_{v\in V} td(G-v)</math>, якщо ''G'' зв'язний і |''G''|>1
* <math>\max_{i} td(G_i)</math> в іншому випадку, де ''V''&nbsp;— множина вершин графа ''G'' і <math>G_i</math>&nbsp;— зв'язні компоненти ''G''{{Sfn|Nešetřil, Ossona de Mendez|2012|с=117,Lemma 6.1}}. Це визначення віддзеркалює визначення [[Циклічний ранг|циклічного рангу]] орієнтованих графів, яке використовує строгу зв'язність і строго пов'язані компоненти замість неорієнтованої зв'язності і зв'язних компонент.

Деревну глибину можна визначити з використанням [[розфарбовування графів]]. '''Центроване розфарбування''' графа&nbsp;— це розфарбування вершин, яка має властивість, що в будь-якому зв'язному [[Породжений підграф|породженому підграфі]] є колір, який зустрічається рівно один раз. Тоді деревна глибина&nbsp;— це найменше число кольорів, необхідних для центрованого розфарбовування графа. Якщо ''F''&nbsp;— ліс з висотою ''d'', який має властивість, що кожне ребро графа ''G'' з'єднує предка і нащадка в дереві, то можна отримати центроване розфарбування графа ''G'' ''d'' кольорами розфарбувавши кожну вершину в колір з номером, рівним відстані від кореня у графі ''F''{{Sfn|Nešetřil, Ossona de Mendez|2012|с=125–128, Section 6.5, "Centered Colorings"}}.

Нарешті, можна визначити його в термінах {{Не перекладено|Фішкова гра на графі|фішкової гри|en|pebble game}}. А саме, точно як гру [[переслідування-ухилення]]. Уявімо таку гру на неорієнтованому графі. Є два гравці, грабіжник і поліцейський. Грабіжник має одну фішку, яку він рухає вздовж ребер графа. Поліцейський має необмежену кількість фішок, але він хоче мінімізувати кількість використаних фішок. Поліцейський не може пересувати своїх фішок, поміщених на граф. Гра відбувається так. Грабіжник розміщує свою фішку, потім поліцейський повідомляє, куди він хоче поставити наступну фішку і грабіжник після цього може пересунути свою фішку вздовж ребер, але не через зайняті вершини. Гра завершується, коли поліцейський поміщає наступну фішку поверх фішки грабіжника. Деревна глибина даного графа визначає найменше число фішок, необхідних для гарантованого виграшу{{Sfn|Gruber, Holzer|2008|с=Theorem 5}}{{Sfn|Hunter|2011|Main Theorem}}. Для [[Зірка (теорія графів)|зірки]] достатньо двох фішок&nbsp;— розміщуємо першу фішку в центрі зірки, змушуючи грабіжника перейти в якийсь промінь, а потім поміщаємо другу фішку на фішку грабіжника. Для [[Шлях (теорія графів)|шляху]] з <math>n</math> вершинами поліцейський використовує стратегію [[Двійковий пошук|двійкового пошуку]], яка гарантує використання не більше <math>\lceil\log_2(n+1)\rceil</math> фішок.

== Приклади ==
[[Файл:Tree-depth.svg|міні|Деревна глибина [[Повний граф|повного графа]] ''K''<sub>4</sub> і [[Повний двочастковий граф|повного двочасткового графа]] ''K''<sub>3,3</sub> дорівнює чотирьом, тоді як деревна глибина [[Шлях (теорія графів)|шляху]] ''P''<sub>7</sub> дорівнює трьом.]]
Деревна глибина [[Повний граф|повного графа]] дорівнює кількості його вершин, і в цьому випадку єдиним можливим лісом ''F'', для якого будь-яка пара вершин перебуває у відношенні предок-нащадок, є одиничний шлях. Схожим чином деревна глибина повного двочасткового графа ''K''<sub>''x'',''y''</sub> дорівнює min(''x'',''y'')&nbsp;+&nbsp;1, і як би ми не розташовували вершини, листки лісу ''F'' повинні мати принаймні min(''x'',''y'') предків ''F''. Ліс, на якому досягається min(''x'',''y'')&nbsp;+&nbsp;1, можна побудувати, утворивши шлях з вершин меншої за розміром частки графа, а вершини більшої частки формують листки дерева ''F'', сполучені з нижньою вершиною шляху.

Деревна глибина шляху з ''n'' вершинами дорівнює рівно <math>\lceil\log_2(n+1)\rceil</math>. Ліс ''F'', що подає цей шлях з такою глибиною, можна утворити, помістивши корінь у середню точку шляху ''F'' і продовжуючи рекурсію в двох менших шляхах з обох боків від кореня{{Sfn|Nešetřil, Ossona de Mendez|2012|с=117, Formula 6.2}}.

== Деревна глибина і зв'язок з деревною шириною ==
{{Див. також|Деревна ширина (теорія графів)}}
Будь-який [[Дерево (теорія графів)|ліс]] із ''n'' вершинами має деревну глибину O(log&nbsp;''n''). Для лісу можна завжди знайти стале число вершин, видалення яких дає ліс, який можна розділити на два менших підліси з максимум 2''n''/3 вершин у кожному. Рекурсивно ділячи ці два підліси, легко можна досягти логарифмічної верхньої межі деревної глибини. Та ж техніка, застосована до [[Деревна декомпозиція|деревної декомпозиції]] графа, показує, що, якщо [[Деревна ширина (теорія графів)|деревна ширина]] ''n''-вершинного графа ''G'' дорівнює ''t'', тоді деревна глибина графа ''G'' дорівнює O(''t''&nbsp;log&nbsp;''n'').{{Sfn|Bodlaender et al|1995}}{{Sfn|Nešetřil, Ossona de Mendez|2012|с=124, Corollary 6.1}} Оскільки [[Зовніпланарний граф|зовніпланарні графи]], [[Паралельно-послідовний граф|паралельно-послідовні графи]] і [[Граф Халіна|графи Халіна]] мають обмежену деревну ширину, вони всі теж мають максимум логарифмічну деревну глибину.

З іншого боку, деревна ширина графа не перевершує його деревної глибини. Точніше, деревна ширина не перевершує [[Шляхова ширина графа|шляхової ширини графа]], яка максимум на одиницю менша від його деревної глибини{{Sfn|Bodlaender et al|1995}}{{Sfn|Nešetřil, Ossona de Mendez|2012|с=123}}.

== Мінори графа ==
[[Мінор графа]] ''G''&nbsp;— це інший граф, утворений з підграфа графа ''G'' стягуванням деяких ребер. Деревна глибина монотонна за мінорами&nbsp;— будь-який мінор графа ''G'' має деревну глибину, що не перевищує деревної глибини самого графа ''G''{{Sfn|Nešetřil, Ossona de Mendez|2012|с=117,Lemma 6.2}}. Таким чином, за [[Теорема Робертсона — Сеймура|теоремою Робертсона&nbsp;— Сеймура]], для будь-якого фіксованого ''d'' множина графів із деревною глибиною, що не перевершує ''d'', має скінченне число [[Характеризація забороненими графами|заборонених мінорів]].

Якщо ''C''&nbsp;— клас графів, замкнутих відносно утворення мінорів, то графи ''C'' мають деревну глибину <math>O(1)</math> [[тоді й лише тоді]], коли ''C'' не включає всіх [[Шлях (граф)|шляхів]]{{Sfn|Nešetřil, Ossona de Mendez|2012|с=122, Proposition 6.4}}.

== Породжені підграфи ==
Деревна глибина має тісний зв'язок з теорією [[Породжений підграф|породжених підграфів]] графа. В класі графів, що мають деревну глибину не більше ''d'' (для будь-якого фіксованого натурального ''d''), властивість бути породженим підграфом є {{Не перекладено|Цілком квазівпорядкованість|цілком квазівпорядкованою|en|well-quasi-ordering}}{{Sfn|Nešetřil, Ossona de Mendez|2012|с=137, Lemma 6.13}}. Основна ідея доведення, що цей зв'язок цілком квазівпорядкований, полягає у використанні індукції за ''d''. Ліси висоти ''d'' можна інтерпретувати як послідовність лісів висоти ''d''&nbsp;−&nbsp;1 (утворених видаленням коренів дерев висоти ''d'') і можна використовувати {{Не перекладено|Лема Гігмана|лему Гігмана|en|Higman's lemma}}, щоб показати, що ці послідовності цілком квазівпорядковані.

Із цілком квазівпорядкованості випливає, що будь-яка властивість графа, монотонна за породженими підграфами, має скінченне число заборонених породжених підграфів, а тому може бути перевірена за поліноміальний час на графах з обмеженою деревною глибиною. Графи з деревною глибиною, що не перевершує ''d'', самі по собі мають скінченне число заборонених породжених підграфів. Нешетрил і Оссона де Мендез{{Sfn|Nešetřil, Ossona de Mendez|2012|с=138. Figure 6.6 on p. 139}} показали 14 заборонених підграфів для графів з деревною шириною три і менше (з посиланням на тези дисертації 2007 року Зденека Дворака).

Якщо ''C'' є класом графів з обмеженою [[Виродженість (теорія графів)|виродженістю]], графи у множині ''C'' мають обмежену деревну ширину тоді і тільки тоді, коли існує шлях, який не може з'явитися як породжений підграф у ''C''{{Sfn|Nešetřil, Ossona de Mendez|2012|с=122, Proposition 6.4}}.

== Складність ==
Визначення глибини дерева є складною обчислювальною задачею&nbsp;— відповідна задача розпізнавання [[NP-повна задача|NP-повна]]{{Sfn|Pothen|1988}}. Завдання залишається NP-повною для [[Двочастковий граф|двочасткових графів]]{{Sfn|Bodlaender et al|1998}}, як і для [[Хордальний граф|хордальних графів]]{{Sfn|Dereniowski, Nadolski|2006}}.

З позитивних моментів&nbsp;— деревну глибину можна обчислити за [[Часова складність|поліноміальний час]] для інтервальних графів{{Sfn|Aspvall, Heggernes|1994}}, як і для графів перестановок, трапецеїдальних графів, графів перетинів дуг кіл, циклічних графів перестановок і графів копорівнянності обмежених розмірностей{{Sfn|Deogun et al|1999}}. Для неорієнтованих дерев деревну глибину можна обчислити за лінійний час{{Sfn|Iyer et al|1988}}{{Sfn|Schäffer|1989}}.

Бодлендер, Гілберт, Хафстейнссон і Клокс{{Sfn|Bodlaender et al|1995}} запропонували [[апроксимаційний алгоритм]] пошуку деревної глибини з апроксимаційним коефіцієнтом <math>O((\log n)^2)</math>. Алгоритм заснований на факті, що деревна глибина логарифмічно залежить від деревної ширини графа.

Оскільки деревна глибина монотонна за мінорами графа, задача її пошуку {{Не перекладено|Параметризована складність|фіксовано-параметрично розв'язна|en|Parameterized complexity}}&nbsp;— існує алгоритм обчислення деревної глибини, що працює за час <math>f(d) n^{O(1)}</math>, де ''d''&nbsp;— глибина даного графа і ''n''&nbsp;— число вершин. Таким чином, для будь-якого фіксованого значення ''d'' задача перевірки, чи не перевершує деревна глибина значення ''d'', може бути розв'язана за поліноміальний час. Конкретніше&nbsp;— залежність від ''n'' у цьому алгоритмі можна зробити лінійною таким чином: будуємо дерево пошуку в глибину і перевіряємо, перевищує глибина дерева величину 2<sup>''d''</sup> чи ні. Якщо перевищує, то глибина дерева більша від ''d'' і задачу роз'язано. Якщо ні, можна скористатись побудовою дерева пошуку на невелику глибину для [[Деревна декомпозиція|декомпозиції дерева]] і стандартною технікою [[Динамічне програмування|динамічного програмування]] для графів з обмеженою деревною шириною, щоб обчислити глибину за лінійний час{{Sfn|Nešetřil, Ossona de Mendez|2012|с=138}}. Більш складний алгоритм розв'язування за лінійний час, заснований на планарності мінорів, що виключаються під час пошуку в глибину, запропонували раніше Бодлендер, Деоган, Дженсен та Клокс{{Sfn|Bodlaender et al|1998}}. Покращений параметричний алгоритм див. у Райдля, Россманіта, Вілламіла і Сікдара{{Sfn|Reidl et al|2014}}.

Можна обчислити глибину дерева точно для графів, значення глибини для яких може бути великим, за час ''O''(''c''<sup>''n''</sup>) з константою ''c'', трохи меншою від 2.{{Sfn|Fomin et al|2013}}

== Примітки ==
{{Reflist|2}}

== Література ==

* {{Стаття|doi=10.1007/BF01934264|author=Bengt Aspvall, Pinar Heggernes|ref=Aspvall, Heggernes|title=Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time|видання=BIT|том=34|issue=4|date=1994|pages=484–509}}.
* {{Стаття|author=Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, Zsolt Tuza|ref=Bodlaender et al|doi=10.1137/S0895480195282550|issue=1|видання=[[SIAM Journal on Discrete Mathematics]]|pages=168–181|title=Rankings of graphs|url=http://www.cs.uu.nl/pub/RUU/CS/techreps/CS-1995/1995-03.pdf|том=11|date=1998}}{{Недоступная ссылка|date=Июнь 2018|bot=InternetArchiveBot}}.
* {{Стаття|author=Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks|ref=Bodlaender et al|doi=10.1006/jagm.1995.1009|issue=2|видання=Journal of Algorithms|pages=238–255|title=Approximating treewidth, pathwidth, frontsize, and shortest elimination tree|id={{Citeseerx|10.1.1.29.7198}}|том=18|date=1995}}.
* {{Стаття|author=Jitender S. Deogun, Ton Kloks, Dieter Kratsch, Haiko Müller|ref=Deogun et al|doi=10.1016/S0166-218X(99)00179-1|title=On the vertex ranking problem for trapezoid, circular-arc and other graphs|видання=Discrete Applied Mathematics|том=98|pages=39–34|date=1999}}.
* {{Стаття|author=D. Dereniowski, A. Nadolski|ref=Dereniowski, Nadolski|doi=10.1016/j.ipl.2005.12.006|title=Vertex rankings of chordal graphs and weighted trees|видання=[[Information Processing Letters]]|том=98|pages=96–100|date=2006}}.
* {{Книга
|автор = Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk
|ref = Fomin et al
|відповідальний = Gregory Gutin, Stefan Szeider
|doi = 10.1007/978-3-319-03898-8_13
|сторінки = 137–149
|серія = Lecture Notes in Computer Science
|заголовок = Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers
|том = 8246
|рік = 2013
}}.
* {{Книга
|автор = Hermann Gruber, Markus Holzer
|ref = Gruber, Holzer
|doi = 10.1007/978-3-540-70583-3_4
|сторінки = 39–50
|видавництво = Springer-Verlag
|серія = Lecture Notes on Computer Science
|заголовок = [[International Colloquium on Automata, Languages and Programming|Proc. 35th International Colloquium on Automata, Languages and Programming]]
|посилання = http://www.hermann-gruber.com/data/icalp08.pdf
|том = 5126
|рік = 2008
|назва = 
|archivedate = 11 липня 2011
|archiveurl = https://web.archive.org/web/20110711163607/http://www.hermann-gruber.com/data/icalp08.pdf
}}.
* {{Книга
|рік = 2011
|автор = Paul Hunter
|ref = Hunter
|видавництво = Springer-Verlag
|серія = Lecture Notes on Computer Science
|том = 6914
|заголовок = 18th [[International Symposium on Fundamentals of Computation Theory]]
|doi = 10.1007/978-3-642-22953-4_19
|сторінки = 217–228
}}
* {{Стаття|author=Ananth V. Iyer, H. Donald Ratliff, Gopalakrishnan Vijayan|ref=Iyer et al|doi=10.1016/0020-0190(88)90194-9|title=Optimal node ranking of trees|видання=[[Information Processing Letters]]|том=28|pages=225–201|date=1988}}.
* {{Книга
|автор = Jaroslav Nešetřil, Patrice Ossona de Mendez
|ref = Nešetřil, Ossona de Mendez
|doi = 10.1007/978-3-642-27875-4
|ISBN = 978-3-642-27874-7
|місце = Heidelberg
|сторінки = 115–144
|видавництво = Springer
|серія = Algorithms and Combinatorics
|заголовок = Sparsity: Graphs, Structures, and Algorithms
|том = 28
|рік = 2012
}}.
* {{Книга
|автор = Alex Pothen
|ref = Pothen
|заголовок = The complexity of optimal elimination trees
|серія = Tech. Report CS-88-13
|видавництво = [[Pennsylvania State University]]
|рік = 1988
}}.
* {{Книга
|автор = Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar
|ref = Reidl et al
|відповідальний = Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias
|doi = 10.1007/978-3-662-43948-7_77
|сторінки = 931–942
|серія = Lecture Notes in Computer Science
|заголовок = [[International Colloquium on Automata, Languages and Programming|Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014, Proceedings, Part I]]
|том = 8572
|рік = 2014
}}.
* {{Стаття|author=Benjamin Rossman|ref=Rossman|doi=10.1145/1379759.1379763|issue=3|видання=[[Journal of the ACM]]|pages=Article 15|title=Homomorphism preservation theorems|том=55|date=2008}}.
* {{Стаття|author=Alejandro A. Schäffer|ref=Schäffer|doi=10.1016/0020-0190(89)90161-0|title=Optimal node ranking of trees in linear time|видання=[[Information Processing Letters]]|том=33|pages=91–19|date=1989}}.
[[Категорія:Теорія мінорів графів]]
[[Категорія:Інваріанти графа]]
[[Категорія:Розфарбування графів]]