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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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