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

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

Определения

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

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

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

{\ displaystyle \ operatorname {td} (G) = {\ begin {cases} 1, & {\ text {if}} | G | = 1; \\ 1+ \ min _ {v \ in V} \ operatorname { td} (Gv), & {\ text {if}} G {\ text {связан и}} | G |> 1; \\\ max _ {i} {\ rm {td}} (G_ {i} ), & {\ text {else}}; \ end {case}}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность

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

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

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

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

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

Languages

In other projects