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

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

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

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

, если |G|=1 , если G связен и |G|>1 в противном случае,

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

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

Наконец, можно определить его в терминах фишечной игры. Точнее, в точности как игра «полицейские-грабители». Представим следующую игру на неориентированном графе. Имеется два игрока, грабитель и полицейский. Грабитель имеет одну фишку, которую он двигает вдоль рёбер графа. Полицейский имеет неограниченное число фишек, но он хочет минимизировать число использованных фишек. Полицейский не может передвигать свои фишки, помещённые на граф. Игра происходит следующим образом. Грабитель размещает свою фишку, затем полицейский сообщает, куда он хочет поставить следующую фишку и грабитель после этого может передвинуть свою фишку вдоль рёбер, но не через занятые вершины. Игра завершается, когда полицейский помещает следующую фишку поверх фишки грабителя. Древовидная глубина данного графа определяет минимальное число фишек, необходимых для гарантированного выигрыша. Для звёзд достаточно двух фишек — размещаем первую фишку в центре звезды, вынуждая грабителя перейти в какой-нибудь луч, а затем помещаем вторую фишку на фишку грабителя. Для пути с вершинами полицейский использует стратегию двоичного поиска, которая гарантирует использование не более фишек.

Примеры

Древовидная глубина полного графа равна числу его вершин, и в этом случае единственным возможным лесом F, для которого любая пара вершин должна быть в отношении предок-потомок, является одиночный путь. Похожим образом древовидная глубина полного двудольного графа Kx,y равна min(x,y) + 1, и как бы мы не располагали вершины, листья леса F должны иметь по меньшей мере min(x,y) предков в F. Лес, на котором достигается min(x,y) + 1, может быть построен путём образования пути из вершин меньшей по размеру доли графа, а вершины большей доли формируют листья дерева F, соединённые с нижней вершиной пути.

Древовидная глубина пути с n вершинами равна в точности . Лес F, представляющий этот путь с такой глубиной, можно образовать, поместив корень в среднюю точку пути F и продолжая рекурсию в двух меньших путях с обеих сторон от корня.

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

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

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

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

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

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

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

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

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

Бодлендер, Гилберт, Хафстейнссон и Клокс предложили аппроксимационный алгоритм поиска древовидной глубины c аппроксимационным коэффициентом . Алгоритм основан на факте, что древовидная глубина логарифмически зависит от древовидной ширины графа.

Поскольку древовидная глубина монотонна по минорам графа, задача её поиска — существует алгоритм вычисления древовидной глубины, работающий за время , где d — древовидная глубина данного графа и n — число вершин. Таким образом, для любого фиксированного значения d задача проверки, не превосходит ли древовидная глубина значение d, может быть решена за полиномиальное время. Конкретнее — зависимость от n в этом алгоритме можно сделать линейной следующим способом: строим дерево поиска в глубину и проверяем, больше древовидная глубина величины 2d или нет. Если больше, древовидная глубина больше d и задача решена. Если нет, можно использовать построение дерева поиска на небольшую глубину для декомпозиции дерева и стандартную технику динамического программирования для графов с ограниченной древовидной шириной, чтобы вычислить глубину за линейное время. Более сложный алгоритм решения за линейное время, основанный на планарности исключаемых миноров при поиске в глубину, был предложен ранее Бодлендером, Деоганом, Дженсеном и Клоксом. Улучшенный параметрический алгоритм см. у Райдля, Россманита, Вилламила и Сикдара.

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

Примечания

Литература . . . . . . .

. . . . . .

Категория:Раскраска графа Категория:Инварианты графов Категория:Теория миноров графов Категория:NP-полные задачи