Древовидная ширина

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

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

Определение

Древовидное разложение графа G = (V, E) — это дерево T, вершинами X1, ..., Xn которого являются подмножества V, удовлетворяющие следующим свойствам, секция 12.3: Объединение всех множеств Xi равно V. Таким образом, любая вершина графа содержится хотя бы в одном множестве. Если Xi и Xj оба содержат вершину v, то все остальные вершины дерева Xk на (единственном) пути из Xi в Xj также содержат v. Это эквивалентно утверждению, что вершины дерева, содержащие v, образуют связное поддерево T. Для любого ребра (v, w) графа G существует подмножество Xi, содержащее и v, и w. То есть вершины смежны в графе если только соответствующие поддеревья имеют общую вершину в дереве T. Ширина разложения дерева — это размер его наибольшего множества Xi минус единица (таким образом у деревьев ширина древовидного разложения 1).

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

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

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

при .

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

Размер минора решётки Поскольку древовидная ширина решётки n × n равна n, древовидная ширина графа G всегда больше или равна размера наибольшей квадратной решётки-минора графа G. В обратном направлении, существует функция f, такая, что древовидная ширина не превосходит f(r), где r — размер наибольшей квадратной решётки-минора. Однако известные границы f не малы: f должна быть не меньше Ω(r2 log r) и не больше 202r5.. Об Ω в нижней оценке смотрите «O» большое и «o» малое. Более строгие границы известны для ограниченных семейств графов, что даёт эффективные алгоритмы для многих задач оптимизации на этих семействах графов по теории . даёт аналог связи между древовидной шириной и размером минора решётки для неограниченных графов.

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

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

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

Примечания

Ссылки

. . . . . . . . . . . . . . . . . . . . . . . . . . .

Категория:Деревья (графы) Категория:Теория миноров графов