Глубина дерева - Tree-depth

Эта статья о инвариант графов. О расстоянии от корня абстрактного дерева см. Дерево (структура данных) § Терминология.

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

Определения

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

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

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

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

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

Глубину дерева также можно определить с помощью формы раскраска графика. А центрированная окраска графа - это раскраска его вершин таким свойством, что каждая связная индуцированный подграф имеет цвет, который появляется ровно один раз. Тогда глубина дерева - это минимальное количество цветов в центрированной раскраске данного графа. Если F лес на высоте d с тем свойством, что каждое ребро грамм соединяет предка и потомка в дереве, затем центрированная окраска грамм с помощью d цвета можно получить, раскрасив каждую вершину по расстоянию от корня ее дерева в F.^[5]

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

Примеры

Древесные глубины полный график K₄ и полный двудольный граф K_3,3 оба четыре, в то время как глубина дерева граф путей п₇ это три.

Древесная глубина полный график равно количеству вершин. Ведь в этом случае единственно возможный лес F для которого каждая пара вершин находится в отношениях предок-потомок, является одним путем. Аналогично, древовидная глубина полный двудольный граф K_Икс,у мин (Икс,у) + 1. For, узлы, расположенные на листьях леса F должно быть не менее min (Икс,у) предки в F. Лес, достигающий этой мин (Икс,у) + 1 границу можно построить, образуя путь для меньшей стороны двудольного деления, при этом каждая вершина на большей стороне двудольного деления образует лист в F соединен с нижней вершиной этого пути.

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

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

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

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

График миноров

А незначительный графа грамм еще один граф, образованный из подграфа грамм за счет сжатия некоторых его краев. Древовидность монотонна под минорами: каждый минор графа грамм имеет глубину дерева не более, чем глубину дерева грамм сам.^[11] Таким образом, Теорема Робертсона – Сеймура, для каждого фиксированного d набор графов с глубиной дерева не более d имеет конечный набор запрещенные несовершеннолетние.

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

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

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

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

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

Если C - класс графов с ограниченными вырождение, графики в C имеют ограниченную древесную глубину тогда и только тогда, когда существует граф путей, который не может быть индуцированным подграфом графа в C.^[12]

Сложность

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

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

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

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

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

Примечания

1. Bodlaender et al. (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. Bodlaender et al. (1995); Нешетржил и Оссона де Мендес (2012), Следствие 6.1, с. 124.
9. Каварабаяши и Россман (2018)
10. Bodlaender et al. (1995); Нешетржил и Оссона де Мендес (2012), п. 123.
11. Нешетржил и Оссона де Мендес (2012), Лемма 6.2, с. 117.
12. Нешетржил и Оссона де Мендес (2012), Предложение 6.4, с. 122.
13. Нешетржил и Оссона де Мендес (2012), Лемма 6.13, с. 137.
14. Нешетржил и Оссона де Мендес (2012), п. 138. Рисунок 6.6 на стр. 139 показаны 14 запрещенных подграфов для графов с глубиной дерева не более трех, зачисленных на соискание степени доктора философии 2007 г. тезис Зденек Дворжак.
15. Потен (1988).
16. Деренёвский и Надольский (2006).
17. Аспвалл и Хеггернес (1994).
18. Деогун и др. (1999).
19. Айер, Ратлифф и Виджаян (1988); Шеффер (1989).
20. Нешетржил и Оссона де Мендес (2012), п. 138. Более сложный алгоритм линейного времени, основанный на планарности исключенных миноров для глубины дерева, был дан ранее формулой Bodlaender et al. (1998). Для улучшенных параметризованных алгоритмов см. Reidl et al. (2014).
21. Фомин, Яннопулу и Пилипчук (2013).

Рекомендации

• Аспвалл, Бенгт; Хеггернес, Пинар (1994), "Поиск деревьев исключения минимальной высоты для интервальных графов за полиномиальное время", КУСОЧЕК, 34 (4): 484–509, Дои:10.1007 / BF01934264.
• Бодландер, Ханс Л.; Деогун, Джитендер С .; Янсен, Клаус; Клокс, Тон; Kratsch, Дитер; Мюллер, Хайко; Туза, Жолт (1998), «Рейтинги графиков» (PDF), Журнал SIAM по дискретной математике, 11 (1): 168–181, Дои:10.1137 / S0895480195282550
• Бодландер, Ханс Л.; Гилберт, Джон Р .; Хафстейнссон, Хьялмтыр; Клокс, Тон (1995), "Приближение ширины дерева, ширины пути, размера фронта и кратчайшего дерева исключения", Журнал алгоритмов, 18 (2): 238–255, CiteSeerX  10.1.1.29.7198, Дои:10.1006 / jagm.1995.1009.
• Деогун, Джитендер С .; Клокс, Тон; Kratsch, Дитер; Мюллер, Хайко (1999), "О проблеме ранжирования вершин для графов трапеции, дуги окружности и других графов", Дискретная прикладная математика, 98: 39–63, Дои:10.1016 / S0166-218X (99) 00179-1.
• Dereniowski, D .; Надольский, А. (2006), "Рейтинг вершин хордовых графов и взвешенных деревьев", Письма об обработке информации, 98: 96–100, Дои:10.1016 / j.ipl.2005.12.006.
• Фомин, Федор В .; Giannopoulou, Archontia C .; Пилипчук, Михал (2013), «Вычисление глубины дерева быстрее, чем 2^п", у Гутина, Грегори; Зейдера, Стефана (ред.), Параметризованные и точные вычисления: 8-й Международный симпозиум, IPEC 2013, София Антиполис, Франция, 4-6 сентября 2013 г., Пересмотренные избранные статьи, Конспект лекций по информатике, 8246, стр. 137–149, arXiv:1306.3857, Дои:10.1007/978-3-319-03898-8_13.
• Грубер, Германн; Хольцер, Маркус (2008), «Конечные автоматы, связность орграфов и размер регулярного выражения» (PDF), Proc. 35-й Международный коллоквиум по автоматам, языкам и программированию, Конспект лекций по информатике, 5126, Springer-Verlag, стр. 39–50, Дои:10.1007/978-3-540-70583-3_4.
• Хантер, Пол (2011), «ЛИФО-поиск по диграфам: игра для поиска циклического ранга», 18-е Международный симпозиум по основам теории вычислений, Конспект лекций по информатике, 6914, Springer-Verlag, стр. 217–228, arXiv:1103.6019, Дои:10.1007/978-3-642-22953-4_19
• Iyer, Ananth V .; Рэтлифф, Х. Дональд; Виджаян, Гопалакришнан (1988), «Оптимальное ранжирование узлов деревьев», Письма об обработке информации, 28: 225–229, Дои:10.1016/0020-0190(88)90194-9.
• Каварабаяси, Кен-ичи; Россман, Бенджамин (2018), "Полиномиальное исключенное второстепенное приближение глубины дерева", Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SIAM, стр. 234–246, Дои:10.1137/1.9781611975031.17.
• Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Глава 6. Деревья с ограниченной высотой и глубиной дерева», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Heidelberg: Springer, стр. 115–144, Дои:10.1007/978-3-642-27875-4, ISBN  978-3-642-27874-7, МИСТЕР  2920058.
• Потен, Алекс (1988), Сложность оптимальных деревьев исключения, Тех. Отчет CS-88-13, Государственный университет Пенсильвании.
• Рейдл, Феликс; Россманиф, Питер; Санчес Вильяамил, Фернандо; Сикдар, Сомнат (2014), «Более быстрый параметризованный алгоритм для глубины дерева», Эспарза, Хавьер; Fraigniaud, Пьер; Хусфельдт, Тор; и другие. (ред.), Автоматы, языки и программирование: 41-й международный коллоквиум, ICALP 2014, Копенгаген, Дания, 8–11 июля 2014 г., Труды, часть I, Конспект лекций по информатике, 8572, стр. 931–942, arXiv:1401.7540, Дои:10.1007/978-3-662-43948-7_77.
• Россман, Бенджамин (2008), "Теоремы сохранения гомоморфизма", Журнал ACM, 55 (3): Статья 15, Дои:10.1145/1379759.1379763.
• Шеффер, Алехандро А. (1989), "Оптимальное ранжирование узлов деревьев за линейное время", Письма об обработке информации, 33: 91–96, Дои:10.1016/0020-0190(89)90161-0, HDL:10338.dmlcz / 140723.