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

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

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

Определения

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

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

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

$$\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}}$$

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

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

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

Примеры

Глубина дерева полного графа $K_{4}$ и полный двудольный граф $K_{3,3}$ оба равны четырем, а глубина дерева графа путей $P_{7}$ это три.

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

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

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

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

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

Миноры графа

Младшая часть графа $G$ это еще один граф, образованный из подграфа $G$ сжимая некоторые его края. Глубина дерева монотонна относительно миноров: каждый минор графа $G$ имеет глубину дерева, не более чем равную глубине дерева $G$ сам. Таким образом, по теореме Робертсона–Сеймура для любого фиксированного $d$ множество графов с глубиной дерева не более $d$ имеет конечное множество запрещенных миноров .

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

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

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

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

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

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

Сложность

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

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

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

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

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

Ссылки

• Аспвалль, Бенгт; Хеггернес, Пинар (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), «О проблеме ранжирования вершин для трапецеидальных, дуговых и других графов», Discrete Applied Mathematics , 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) , Proc. 35-й Международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике, том. 5126, Springer-Verlag, стр. 39–50, номер документа : 10.1007/978-3-540-70583-3_4 , ISBN.  978-3-540-70582-6 .
• Хантер, Пол (2011), «LIFO-поиск по орграфам: игра с поиском циклического ранга», 18-й Международный симпозиум по основам теории вычислений , Конспекты лекций по информатике, том. 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 .
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Глава 6. Деревья ограниченной высоты и глубина дерева», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, стр. 115–144, номер документа : 10.1007/978-3-642-27875-4 , ISBN.  978-3-642-27874-7 , МР   2920058 .
• Потен, Алекс (1988), Сложность оптимальных деревьев исключения , Tech. Отчет CS-88-13, Университет штата Пенсильвания .
• Рейдл, Феликс; Россманит, Питер; Санчес Вильямиль, Фернандо; Сикдар, Сомнат (2014), «Более быстрый параметризованный алгоритм определения глубины дерева», Эспарса, Хавьер; Френьио, Пьер; Хусфельдт, Тор; и др. (ред.), Автоматы, языки и программирование: 41-й международный коллоквиум, ICALP 2014, Копенгаген, Дания, 8–11 июля 2014 г., Материалы, часть I , Конспекты лекций по информатике, том. 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 .