Глубина дерева (теория графов)

В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков[1][2][3]. Интуитивно, если древесная ширина графа измеряет, насколько граф далёк от дерева, глубина дерева измеряет, насколько граф далёк от звезды.

Определения

Глубину дерева графа G можно определить как минимальную высоту леса F со свойством, что любое ребро графа G соединяет пару вершин, связанных отношением предок-потомок в F[4]. Если G связен, этот лес должен быть единственным деревом. Лес не обязательно должен быть подграфом графа G, но если является, то это дерево Тремо для G.

Множество пар предок-потомок в F образует тривиально совершенный граф, и высота F является размером наибольшей клики этого графа. Таким образом, глубину дерева можно альтернативно определить как размер наибольшей клики в тривиально совершенном суперграфе графа G, что является зеркальным отражением древесной ширины, которая на единицу меньше размера наибольшей клики в хордальном суперграфе графа G [5]

Другое определение следующее:

${\displaystyle td(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[6]. Это определение зеркально отражает определение циклического ранга ориентированных графов, которое использует строгую связность и строго связанные компоненты вместо неориентированной связности и связных компонент.

Глубину дерева можно определить с использованием раскраски графов. Центрированная раскраска графа — это раскраска вершин, имеющая свойство, что в любом связном порождённом подграфе есть цвет, который встречается ровно один раз. Тогда глубина дерева — это минимальный размер цветов, необходимых для центрированной раскраски графа. Если F — лес с высотой d, имеющий свойство, что любое ребро графа G соединяет предка и потомка в дереве, то можно получить центрированную раскраску графа G d цветами путём раскрашивания каждой вершины в цвет с номером, равным расстоянию от корня в графе F[7].

Наконец, можно определить его в терминах фишечной игры. Точнее, в точности как игра «полицейские-грабители». Представим следующую игру на неориентированном графе. Имеется два игрока, грабитель и полицейский. Грабитель имеет одну фишку, которую он двигает вдоль рёбер графа. Полицейский имеет неограниченное число фишек, но он хочет минимизировать число использованных фишек. Полицейский не может передвигать свои фишки, помещённые на граф. Игра происходит следующим образом. Грабитель размещает свою фишку, затем полицейский сообщает, куда он хочет поставить следующую фишку и грабитель после этого может передвинуть свою фишку вдоль рёбер, но не через занятые вершины. Игра завершается, когда полицейский помещает следующую фишку поверх фишки грабителя. Глубина дерева данного графа определяет минимальное число фишек, необходимых для гарантированного выигрыша[8][9]. Для звёзд достаточно двух фишек — размещаем первую фишку в центре звезды, вынуждая грабителя перейти в какой-нибудь луч, а затем помещаем вторую фишку на фишку грабителя. Для пути с ${\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 и продолжая рекурсию в двух меньших путях с обеих сторон от корня[10].

Глубина деревьев и связь с древесной шириной

Любой лес с n вершинами имеет древесную глубину O(log n). Для леса можно всегда найти постоянное число вершин, удаление которых даёт лес, который можно разделить на два меньших подлеса с максимум 2n/3 вершин в каждом. Рекурсивно деля эти два подлеса, легко можно достичь логарифмическую верхнюю границу древесной глубины. Та же техника, применённая к декомпозиции дерева графа, показывает, что если древесная ширина n-вершинного графа G равна t, тогда древесная глубина графа G равна O(t log n).[11][12] Поскольку внешнепланарные графы, параллельно-последовательные графы и графы Халина имеют ограниченную ширину деревьев, они все тоже имеют максимум логарифмическую глубину деревьев.

В другом направлении ширина дерева графа не превосходит его глубину дерева. Точнее, ширина дерева не превосходит путевую ширину графа, которая максимум на единицу меньше его глубины дерева[11][13].

Миноры графа

Минор графа G — это другой граф, образованный из подграфа графа G стягиванием некоторых рёбер. Глубина дерева монотонна по минорам — любой минор графа G имеет глубину дерева, не превосходящую глубину дерева самого графа G[14]. Таким образом, по теореме Робертсона-Сеймура, для любого фиксированного d множество графов с глубиной дерева, не превосходящей d, имеет конечное число запрещённых миноров.

Если C — класс графов, замкнутых относительно образования миноров, то графы в C имеют древесную глубину ${\displaystyle O(1)}$ тогда и только тогда, когда C не включает все пути[15].

Порождённые подграфы

Древесная глубина имеет тесную связь с теорией порождённых подграфов графа. В классе графов, имеющих древесную глубину не более d (для любого фиксированного натурального d), свойство быть порождённым подграфом является вполне квазиупорядоченным^[англ.][16]. Основная идея доказательства, что эта связь вполне квазиупорядоченна, заключается в использовании индукции по d. Леса высоты d можно интерпретировать как последовательность лесов высоты d − 1 (образованных удалением корней деревьев высоты d) и можно использовать лемму Хигмана^[англ.], чтобы показать, что эти последовательности вполне квазиупорядоченны.

Из вполне квазиупорядоченности вытекает, что любое свойство графа, монотонное по порождённым подграфам, имеет конечное число запрещённых порождённых подграфов, а потому может быть проверено за полиномиальное время на графах с ограниченной древесной глубиной. Графы с древесной глубиной, не превосходящей d, сами по себе имеют конечное число запрещённых порождённых подграфов. Нешетрил и Оссона де Мендез[17] показали 14 запрещённых подграфов для графов с древесной шириной три и менее (со ссылкой на тезисы диссертации 2007 года Зденека Дворака).

Если C является классом графов с ограниченной вырожденностью, графы в множестве C имеют ограниченную древесную ширину тогда и только тогда, когда существует путь, который не может появиться в качестве порождённого подграфа в C[15].

Сложность

Определение глубины дерева является сложной вычислительной задачей — соответствующая задача распознавания NP-полна[18]. Задача остаётся NP-полной для двудольных графов[1], как и для хордальных графов[19].

Из положительных моментов — глубина дерева может быть вычислена за полиномиальное время для интервальных графов[20], как и для перестановочных графов, трапецеидальных графов, графов пересечений дуг окружностей, циклических перестановочных графов и графов косравнимости ограниченных размерностей[21]. Для неориентированных деревьев глубина дерева может быть вычислена за линейное время[22][23].

Бодлендер, Гилберт, Хафстейнссон и Клокс[11] предложили аппроксимационный алгоритм поиска глубины дерева c аппроксимационным коэффициентом ${\displaystyle O((\log n)^{2})}$. Алгоритм основан на факте, что глубина дерева логарифмически зависит от древесной ширины графа.

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

Можно вычислить глубину дерева точно для графов, значение глубины для которых может быть велико, за время O(c^n) с константой c, чуть меньшей 2.[26]

Примечания

1. Bodlaender et al, 1998.
2. Rossman, 2008.
3. Nešetřil, Ossona de Mendez, 2012, p. 116.
4. Nešetřil, Ossona de Mendez, 2012, с. 115, Definition 6.1.
5. David Eppstein. Graph parameters and cliques in supergraphs. — 2012 (November 15). Архивировано 9 января 2014 года..
6. Nešetřil, Ossona de Mendez, 2012, p. 117,Lemma 6.1.
7. Nešetřil, Ossona de Mendez, 2012, p. 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, p. 117, Formula 6.2.
11. Bodlaender et al, 1995.
12. Nešetřil, Ossona de Mendez, 2012, p. 124, Corollary 6.1.
13. Nešetřil, Ossona de Mendez, 2012, p. 123.
14. Nešetřil, Ossona de Mendez, 2012, p. 117,Lemma 6.2.
15. Nešetřil, Ossona de Mendez, 2012, p. 122, Proposition 6.4.
16. Nešetřil, Ossona de Mendez, 2012, p. 137, Lemma 6.13.
17. Nešetřil, Ossona de Mendez, 2012, p. 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, p. 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. — С. 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. — С. 168–181. — doi:10.1137/S0895480195282550. (недоступная ссылка).
• 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. — С. 238–255. — doi:10.1006/jagm.1995.1009..
• 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. — С. 39–34. — doi:10.1016/S0166-218X(99)00179-1..
• D. Dereniowski, A. Nadolski. Vertex rankings of chordal graphs and weighted trees // Information Processing Letters. — 2006. — Т. 98. — С. 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. Proc. 35th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 2008. — Т. 5126. — С. 39–50. — (Lecture Notes on Computer Science). — doi:10.1007/978-3-540-70583-3_4..
• Paul Hunter. 18th International Symposium on Fundamentals of Computation Theory. — 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 // Information Processing Letters. — 1988. — Т. 28. — С. 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). — ISBN 978-3-642-27874-7. — 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. Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014, Proceedings, Part I / 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 // Journal of the ACM. — 2008. — Т. 55, вып. 3. — С. Article 15. — doi:10.1145/1379759.1379763..
• Alejandro A. Schäffer. Optimal node ranking of trees in linear time // Information Processing Letters. — 1989. — Т. 33. — С. 91–19. — doi:10.1016/0020-0190(89)90161-0..