Глубина дерева

Числовой инвариант графиков

В теории графов глубина дерева связного неориентированного графа является числовым инвариантом , минимальной высоты дерева Тремо для суперграфа . Этот инвариант и его близкие родственники известны в литературе под разными названиями, включая число рангов вершин, упорядоченное хроматическое число и минимальную высоту дерева исключения; он также тесно связан с рангом цикла ориентированных графов и высотой звезды регулярных языков . [ ^1] Интуитивно понятно, что если ширина дерева графа измеряет, насколько он далек от того, чтобы быть деревом , этот параметр измеряет, насколько граф далек от того, чтобы быть звездой . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Определения

Глубину дерева графа можно определить как минимальную высоту леса со свойством, что каждое ребро соединяет пару узлов, которые имеют отношение предок-потомок друг к другу в . ^[2] Если является связным, этот лес должен быть одним деревом; он не обязательно должен быть подграфом , но если это так, то он является деревом Тремо для . ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Множество пар предок-потомок в образует тривиально совершенный граф , а высота — это размер наибольшей клики в этом графе. Таким образом, глубина дерева может быть альтернативно определена как размер наибольшей клики в тривиально совершенном суперграфе , отражая определение ширины дерева как единицы, меньшей размера наибольшей клики в хордальном суперграфе . ^[3] ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G}$

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

$${\displaystyle \operatorname {td} (G)={\begin{cases}1,&{\text{if }}|G|=1;\\1+\min _{v\in V}\operatorname {td} (G-v),&{\text{if }}G{\text{ is connected and }}|G|>1;\\\max _{i}{\rm {td}}(G_{i}),&{\text{otherwise}};\end{cases}}}$$

где — множество вершин , а — связные компоненты . ^[4] Это определение отражает определение ранга цикла ориентированных графов, которое использует сильную связность и сильно связные компоненты вместо ненаправленной связности и связных компонентов. ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle G_{i}}$ ${\displaystyle G}$

Глубина дерева также может быть определена с использованием формы раскраски графа . Центрированная раскраска графа — это раскраска его вершин со свойством, что каждый связанный индуцированный подграф имеет цвет, который появляется ровно один раз. Тогда глубина дерева — это минимальное количество цветов в центрированной раскраске данного графа. Если — лес высоты со свойством, что каждое ребро из соединяет предка и потомка в , то центрированная раскраска с использованием цветов может быть получена путем раскраски каждой вершины по ее расстоянию от корня ее дерева в . ^[5] ${\displaystyle F}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle F}$

Наконец, можно определить это в терминах игры в камешки , или, точнее, как игру в полицейских и грабителей . Рассмотрим следующую игру, сыгранную на неориентированном графе. Есть два игрока, грабитель и полицейский. У грабителя есть один камешек, который он может перемещать по ребрам данного графа. У полицейского есть неограниченное количество камешков, но он хочет минимизировать количество используемых камешков. Полицейский не может перемещать камешек после того, как он был помещен на граф. Игра продолжается следующим образом. Грабитель размещает свой камешек. Затем полицейский объявляет, куда он хочет поместить новый камешек полицейского. Затем грабитель может перемещать свой камешек по ребрам, но не через занятые вершины. Игра заканчивается, когда игрок-полицейский помещает камешек на камешек грабителя. Глубина дерева данного графа — это минимальное количество камешков, необходимое полицейскому для гарантированной победы. ^[6] Для звездного графа достаточно двух камешков: стратегия заключается в том, чтобы поместить камешек в центральную вершину, заставив грабителя взять одну руку, а затем поместить оставшийся камешек на грабителя. Для пути с вершинами полицейский использует стратегию бинарного поиска , которая гарантирует, что потребуется не более камешков. ${\displaystyle n}$ ${\displaystyle \lceil \log _{2}(n+1)\rceil }$

Примеры

Древесная глубина полного графа и полного двудольного графа равна четырем, тогда как древесная глубина путевого графа равна трем. ${\displaystyle K_{4}}$ ${\displaystyle K_{3,3}}$ ${\displaystyle P_{7}}$

Глубина дерева полного графа равна числу его вершин. В этом случае единственный возможный лес, для которого каждая пара вершин находится в отношениях предок-потомок, — это один путь. Аналогично, глубина дерева полного двудольного графа равна . В результате узлы, размещенные в листьях леса, должны иметь по крайней мере предков в . Лес, достигающий этой границы, может быть построен путем формирования пути для меньшей стороны двудольного разбиения, при этом каждая вершина на большей стороне двудольного разбиения образует лист в , соединенный с нижней вершиной этого пути. ${\displaystyle F}$ ${\displaystyle K_{x,y}}$ ${\displaystyle \min(x,y)+1}$ ${\displaystyle F}$ ${\displaystyle \min(x,y)}$ ${\displaystyle F}$ ${\displaystyle \min(x,y)+1}$ ${\displaystyle F}$

Глубина дерева пути с вершинами равна точно . Лес, представляющий этот путь с этой глубиной, может быть сформирован путем размещения средней точки пути в качестве корня и рекурсии в пределах двух меньших путей по обе стороны от него. ^[7] ${\displaystyle n}$ ${\displaystyle \lceil \log _{2}(n+1)\rceil }$ ${\displaystyle F}$ ${\displaystyle F}$

Глубина деревьев и отношение к ширине дерева

Любой -вершинный лес имеет древовидную глубину . Ведь в лесу всегда можно найти постоянное число вершин, удаление которых оставляет лес, который можно разбить на два меньших подлеска с не более чем вершинами в каждом. Рекурсивно разбивая каждый из этих двух подлесков, можно легко вывести логарифмическую верхнюю границу древовидной глубины. Тот же метод, примененный к древовидной декомпозиции графа, показывает, что если древовидная ширина -вершинного графа равна , то древовидная глубина равна . ^[8] Поскольку внешнепланарные графы , последовательно-параллельные графы и графы Халина имеют ограниченную древовидную ширину, все они также имеют не более логарифмическую древовидную глубину. Типичные графы с большой древовидной глубиной и малой древовидной шириной — это идеальные бинарные деревья и пути. Точнее, существует константа со следующим свойством: если граф имеет treedepth не менее и treewidth меньше , то он содержит идеальное бинарное дерево с высотой или путем длины в качестве минора. ^[9] ${\displaystyle n}$ ${\displaystyle O(\log n)}$ ${\displaystyle 2n/3}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle G}$ ${\displaystyle O(t\log n)}$ ${\displaystyle C}$ ${\displaystyle Ck^{5}\log ^{2}k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$

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

Графические несовершеннолетние

Минор графа — это другой граф, образованный из подграфа путем сжатия некоторых его ребер. Древесная глубина монотонна относительно миноров: каждый минор графа имеет древесную глубину, не превышающую его собственную . ^[11] Таким образом, по теореме Робертсона–Сеймура для каждого фиксированного множества графов с древесной глубиной не более имеет конечное множество запрещенных миноров . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle d}$

Если — класс графов, замкнутый относительно взятия миноров графа, то графы в имеют древовидную глубину тогда и только тогда, когда не включают все графы путей . ^[12] Точнее, существует константа такая, что каждый граф древовидной глубины содержит по крайней мере один из следующих миноров (каждый из которых имеет древовидную глубину по крайней мере ): ^[9] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle O(1)}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle c}$ ${\displaystyle k^{c}}$ ${\displaystyle k}$

• сетка , ${\displaystyle k\times k}$
• полное бинарное дерево высоты , ${\displaystyle k}$
• путь порядка . ${\displaystyle 2^{k}}$

Индуцированные подграфы

Помимо того, что древовидная глубина хорошо себя ведет под графовыми минорами, она тесно связана с теорией индуцированных подграфов графа. В классе графов, имеющих древовидную глубину не более (для любого фиксированного целого числа ), отношение быть индуцированным подграфом образует хорошо-квази-упорядочение . ^[13] Основная идея доказательства того, что это отношение является хорошо-квази-упорядочением, заключается в использовании индукции по ; леса высоты можно интерпретировать как последовательности лесов высоты (образованные путем удаления корней деревьев в лесу высоты), и лемму Хигмана можно использовать вместе с гипотезой индукции, чтобы показать, что эти последовательности хорошо-квази-упорядочены. ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d-1}$ ${\displaystyle d}$

Хорошо-квази-упорядочение подразумевает, что любое свойство графов, которое является монотонным относительно индуцированных подграфов, имеет конечное число запрещенных индуцированных подграфов, и, следовательно, может быть проверено за полиномиальное время на графах с ограниченной глубиной дерева. Графы с глубиной дерева не более сами по себе также имеют конечное множество запрещенных индуцированных подграфов. ^[14] ${\displaystyle d}$

Если — класс графов с ограниченной вырожденностью , то графы в имеют ограниченную глубину дерева тогда и только тогда, когда существует граф путей, который не может возникнуть как индуцированный подграф графа в . ^[12] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Сложность

Вычисление глубины дерева является вычислительно сложным: соответствующая задача принятия решения является NP-полной . ^[15] Задача остается NP-полной для двудольных графов (Bodlaender et al. 1998), а также для хордовых графов . ^[16]

С положительной стороны, глубину дерева можно вычислить за полиномиальное время на интервальных графах ^[17] , а также на графах перестановок, трапеций, дуг окружности, круговых перестановочных графах и графах сопоставимости ограниченной размерности. ^[18] Для неориентированных деревьев глубину дерева можно вычислить за линейное время. ^[19]

Бодлендер и др. (1995) предлагают алгоритм аппроксимации глубины дерева с коэффициентом аппроксимации , основанный на том факте, что глубина дерева всегда находится в пределах логарифмического множителя ширины дерева графа. ${\displaystyle O((\log n)^{2})}$

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

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

Примечания

1. Бодлендер и др. (1998); Россман (2008); Нешетржил и Оссона де Мендес (2012), с. 116.
2. Нешетржил и Оссона де Мендес (2012), Определение 6.1, стр. 115.
3. Эппштейн, Дэвид (15 ноября 2012 г.), Параметры графа и клики в суперграфах.
4. Нешетржил и Оссона де Мендес (2012), Лемма 6.1, стр. 117.
5. Нешетржил и Оссона де Мендес (2012), Раздел 6.5, «Центрированные раскраски», стр. 125–128.
6. Грубер и Хольцер (2008), Теорема 5, Хантер (2011), Основная теорема.
7. Нешетржил и Оссона де Мендес (2012), Формула 6.2, стр. 117.
8. Бодлендер и др. (1995); Нешетржил и Оссона де Мендес (2012), следствие 6.1, с. 124.
9. Каварабаяши и Россман (2018)
10. Бодлендер и др. (1995); Нешетржил и Оссона де Мендес (2012), с. 123.
11. Нешетржил и Оссона де Мендес (2012), Лемма 6.2, с. 117.
12. Nešetřil & Ossona de Mendez (2012), Предложение 6.4, стр. 122.
13. Нешетржил и Оссона де Мендес (2012), Лемма 6.13, с. 137.
14. Nešetřil & Ossona de Mendez (2012), стр. 138. На рисунке 6.6 на стр. 139 показаны 14 запрещенных подграфов для графов с глубиной дерева не более трех, приписываемых докторской диссертации 2007 года Зденека Дворжака .
15. Потен (1988).
16. Деренёвски и Надольски (2006).
17. Аспвалл и Хеггернес (1994).
18. Деогун и др. (1999).
19. Айер, Рэтлифф и Виджаян (1988); Шеффер (1989).
20. Nešetřil & Ossona de Mendez (2012), стр. 138. Более сложный алгоритм линейного времени, основанный на планарности исключенных миноров для глубины дерева, был предложен ранее Bodlaender et al. (1998). Для улучшенных параметризованных алгоритмов см. Reidl et al. (2014).
21. Фомин, Яннопулу и Пилипчук (2013).

Ссылки

• Аспвалл, Бенгт; Хеггернес, Пинар (1994), «Поиск деревьев исключения минимальной высоты для интервальных графов за полиномиальное время», BIT , 34 (4): 484–509, doi :10.1007/BF01934264, S2CID  16141974.
• Бодлендер, Ханс Л .; Деогун, Джитендер С.; Янсен, Клаус; Клокс, Тон; Крач, Дитер; Мюллер, Хайко; Туза, Жолт (1998), «Рейтинги графов» (PDF) , SIAM Journal on Discrete Mathematics , 11 (1): 168–181, doi : 10.1137/S0895480195282550
• Бодлендер, Ханс Л .; Гилберт, Джон Р.; Хафштейнссон, Хьялмтир; Клокс, Тон (1995), «Аппроксимация ширины дерева, ширины пути, фронтального размера и кратчайшего дерева исключения», Journal of Algorithms , 18 (2): 238–255, CiteSeerX  10.1.1.29.7198 , doi : 10.1006/jagm.1995.1009.
• Деогун, Джитендер С.; Клокс, Тон; Кратч, Дитер; Мюллер, Хайко (1999), «О проблеме ранжирования вершин для трапециевидных, дуговых и других графов», Дискретная прикладная математика , 98 (1–2): 39–63, doi : 10.1016/S0166-218X(99)00179-1.
• Деренёвски, Д.; Надольски, А. (2006), «Ранжирование вершин хордовых графов и взвешенных деревьев», Information Processing Letters , 98 (3): 96–100, doi :10.1016/j.ipl.2005.12.006.
• Фомин, Федор В.; Джаннопулу, Архонтия К.; Пилипчук, Михал (2013), «Вычисление глубины дерева быстрее, чем 2 ⁿ », в Гутин, Грегори; Сейдер, Стефан (ред.), Параметризованные и точные вычисления: 8-й международный симпозиум, IPEC 2013, София Антиполис, Франция, 4-6 сентября 2013 г., Пересмотренные избранные статьи , Конспект лекций по информатике, т. 8246, стр. 137–149, arXiv : 1306.3857 , doi :10.1007/978-3-319-03898-8_13, ISBN 978-3-319-03897-1.
• Грубер, Герман; Хольцер, Маркус (2008), «Конечные автоматы, связность орграфов и размер регулярных выражений» (PDF) , Труды 35-го Международного коллоквиума по автоматам, языкам и программированию , Конспект лекций по информатике, том 5126, Springer-Verlag, стр. 39–50, doi :10.1007/978-3-540-70583-3_4, ISBN 978-3-540-70582-6.
• Хантер, Пол (2011), «LIFO-поиск в орграфах: поисковая игра для ранга цикла», 18-й Международный симпозиум по основам теории вычислений , Lecture Notes on Computer Science, т. 6914, Springer-Verlag, стр. 217–228, arXiv : 1103.6019 , doi : 10.1007/978-3-642-22953-4_19, ISBN 978-3-642-22952-7, S2CID  14278138
• Айер, Анант В.; Рэтлифф, Х. Дональд; Виджаян, Гопалакришнан (1988), «Оптимальное ранжирование узлов деревьев», Information Processing Letters , 28 (5): 225–229, doi :10.1016/0020-0190(88)90194-9.
• Каварабаяси, Кен-ичи ; Россман, Бенджамин (2018), «Полиномиальная аппроксимация исключенных миноров глубины дерева», Труды двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , SIAM, стр. 234–246, doi : 10.1137/1.9781611975031.17 , ISBN 978-1-61197-503-1.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Глава 6. Деревья ограниченной высоты и глубины дерева", Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Гейдельберг: Springer, стр. 115–144, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058.
• Потен, Алекс (1988), Сложность оптимальных деревьев исключения , Технический отчет CS-88-13, Университет штата Пенсильвания.
• Reidl, Felix; Rossmanith, Peter; Sánchez Villaamil, Fernando; Sikdar, Somnath (2014), "Быстрый параметризованный алгоритм для treedepth", в Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; et al. (ред.), Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Копенгаген, Дания, 8–11 июля 2014 г., Proceedings, Часть I , Lecture Notes in Computer Science, т. 8572, стр. 931–942, arXiv : 1401.7540 , doi : 10.1007/978-3-662-43948-7_77, ISBN 978-3-662-43947-0, S2CID  7235055.
• Россман, Бенджамин (2008), «Теоремы сохранения гомоморфизма», Журнал ACM , 55 (3): Статья 15, doi :10.1145/1379759.1379763, S2CID  306577.
• Шеффер, Алехандро А. (1989), «Оптимальное ранжирование узлов деревьев за линейное время», Information Processing Letters , 33 (2): 91–96, doi :10.1016/0020-0190(89)90161-0.