Древесная ширина (теория графов)

В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга. Древесная ширина часто используется в качестве параметра в анализе параметрической сложности алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева.

Понятие ширины дерева ввёл Халин (Halin 1976) основываясь на другом параметре, числе Хадвигера, с которым древесная ширина имеет ряд общих свойств. Позже древесную ширину переоткрыли Робертсон и Сеймур, и с тех пор она изучалась многими авторами.

Определение

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

Древесное разложение графа G = (V, E) — это дерево T, вершинами X₁, ..., X_n которого являются подмножества V, удовлетворяющие следующим свойствам:

1. Объединение всех множеств X_i равно V. Таким образом, любая вершина графа содержится хотя бы в одном множестве.
2. Если X_i и X_j оба содержат вершину v, то все остальные вершины дерева X_k на (единственном) пути из X_i в X_j также содержат v. Это эквивалентно утверждению, что вершины дерева, содержащие v, образуют связное поддерево T.
3. Для любого ребра (v, w) графа G существует подмножество X_i, содержащее и v, и w. То есть вершины смежны в графе если только соответствующие поддеревья имеют общую вершину в дереве T.

Ширина разложения дерева — это размер его наибольшего множества X_i минус единица (таким образом у деревьев ширина древесного разложения 1).

Древесная ширина tw(G) графа G — это минимальная ширина всех возможных разложений графа G. В этом определении из размера множества вычитается единица чтобы древесная ширина дерева была равна единице.

Таким же образом, древесная ширина G на единицу меньше размера наибольшей клики в хордальном графе с минимальным кликовым числом, содержащий G. Хордальный граф с этим кликовым числом можно получить, если добавить в G рёбра между любыми двумя вершинами, если обе принадлежат одному и тому же (хотя бы одному) множеству X_i.

Древесную ширину можно описать также в терминах убежищ, функций, описывающих стратегии уклонения для некоторых игр преследования на графе. Граф G имеет древесную ширину k в том и только в том случае, когда в нём есть убежище порядка k + 1, но нет убежища с большим порядком. Здесь убежище порядка k + 1 — это функция β, которая отображает каждое множество X с максимум k вершинами в G в одну из связных компонент графа G \ X и для которой выполняется свойство монотонности

$\beta (Y)\subseteq \beta (X)$ при $X\subseteq Y$.

Ежевика порядка четыре на 3×3 графе-решётке, существование которой показывает, что граф имеет древесную ширину как минимум  3

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

Примеры

Любой полный граф K_n имеет древесную ширину n − 1. Это легче всего видеть, если использовать определение древесной ширины в терминах хордальных графов — полный граф уже хордален, и добавление рёбер не может уменьшить размер наибольшей клики.

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

Ограниченная древесная ширина

Семейства графов деревьев ограниченной ширины

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

Планарные графы не имеют ограниченной древесной ширины, поскольку n × n решётка — это планарный граф, имеющий древесную ширину в точности n. Таким образом, если F — это семейство минорно-замкнутых графов с ограниченной древесной шириной, оно не может включать всех планарных графов. Обратно, если некоторый планарный граф не может быть минором графов в семействе F, то существует константа k, такая что все графы в F имеют древесную ширину не больше k. Таким образом, следующие три условия эквивалентны друг другу:

1. F — семейство минорно-замкнутых графов ограниченной древесной ширины;
2. Один из конечного числа запретных миноров для F планарен;
3. F является семейством минорно-замкнутых графов, включающим не планарные графы.

Запрещённые миноры

Четыре запретных минора для древесной ширины 3

Для любого конечного значения k графы с древесной шириной, не превосходящей k, можно описать конечным числом запрещённых миноров, каждый из которых включает по меньшей мере один планарный граф.

• Для k = 1 единственным запрещённым минором является цикл с 3 вершинами.
• Для k = 2 единственным запрещённым минором является полный граф K ₄ с 4 вершинами.
• Для k = 3 существует четыре запрещённых минора — K₅, граф октаэдра, граф пятиугольной призмы и граф Вагнера. Два из перечисленных полиэдральных графа являются планарными.

Для больших значений k число запрещённых миноров растёт по крайней мере как экспонента от k. Однако известные верхние границы размера и числа запрещённых миноров много выше этой нижней границы.

Алгоритмы

Вычисление ширины дерева

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

На практике алгоритм Шойхета и Гайгера (Shoikhet, Geiger 1997) может найти древесную ширину графов, имеющих размер до 100 вершин и древесную ширину вплоть до 11, путём нахождения хордального дополнения этих графов с оптимальной древесной шириной.

Решение других задач на графах с малой шириной дерева

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

Как пример, задача раскраски графа древесной ширины k может быть решена с помощью динамического программирования на древесном разложении графа. Для каждого множества X_i древесного разложения и каждого разбиения вершин X_i на цвета алгоритм определяет, допустима ли полученная раскраска и может ли она быть расширена на все производные вершины разложения путём комбинирования информации одинакового типа и запоминания в этих вершинах. Результирующий алгоритм находит оптимальную раскраску графа с n вершинами за время O(k^k + O(1)n), что делает эту задачу параметрически сложной с фиксированным параметром.

Связанные параметры

Путевая ширина

Путевая ширина графа имеет очень похожее на древесную ширину определение через древесное разложение, но ограничивается только теми разложениями, в которых результирующее дерево является путём. Другим способом можно определить путевую ширину исходя из интервального графа подобно определению древесной ширины с помощью хордальных графов. Как следствие, путевая ширина графа как минимум не меньше его древесной ширины, но может быть больше только на логарифмический множитель. Ещё один параметр, ширина полосы графа, имеет похожее определение, опирающееся на правильные интервальные графы, и значение параметра не меньше путевой ширины. Кроме того, есть глубина дерева, число, ограниченное для минорно-замкнутых графов тогда и только тогда, когда семейство не включает все графы-пути, и вырожденность, мера разреженности графа, не превосходящая древесную ширину.

Размер минора решётки

Поскольку древесная ширина решётки n × n равна n, древесная ширина графа G всегда больше или равна размера наибольшей квадратной решётки-минора графа G. В обратном направлении, существует функция f, такая, что древесная ширина не превосходит f(r), где r — размер наибольшей квадратной решётки-минора. Однако известные границы f не малы: f должна быть не меньше Ω(r² log r) и не больше 20^2r5. Более строгие границы известны для ограниченных семейств графов, что даёт эффективные алгоритмы для многих задач оптимизации на этих семействах графов по теории двухмерности. Теорема Халина о решётках даёт аналог связи между древесной шириной и размером минора решётки для неограниченных графов.

Диаметр и локальная древесная ширина

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

Некоторые классы графов, не замкнутые относительно миноров, всё же имеют ограниченную локальную древесную ширину. В частности, это 1-планарные графы, то есть графы, которые можно нарисовать на плоскости с максимум одним пересечением одного ребра, и более общие графы, которые можно нарисовать на поверхности ограниченного рода с ограниченным числом пересечений рёбер. Как и в случае семейств минорно-замкнутых графов с ограниченной локальной древесной ширины, это свойство прокладывает путь к эффективным аппроксимационным алгоритмам для таких графов.

Число Хадвигера и S-функции

Халин (Halin 1976) определяет класс параметров графов, который он называет S-функциями, и этот класс включает ширину дерева. Эти функции имеют в качестве области определения графы, а в качестве области значений — целые числа, и они должны принимать значение нуль на графах без рёбер и должны быть монотонными относительно миноров, то есть увеличиваться на единицу при добавлении новой вершины, которая смежна всем предыдущим вершинам. Требуется также, чтобы значение функции от графа было равно большему из значений на двух подмножествах, пересечение которых является вершинным сепаратором и кликой одновременно. Множество всех таких функций образует полную решётку по отношению к операциям поэлементной минимизации и максимизации. Верхний элемент в этой решётке — древесная ширина, а нижний — число Хадвигера, размер максимального полного минора в заданном графе.