Введение

Число, обозначающее близость графа к дереву.

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

Примеры

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

Запрещенные несовершеннолетние

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

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

NP-полной задачей является определение, имеет ли данный граф G ширину дерева не более заданной переменной k. Однако, когда k – любая фиксированная константа, графы с шириной дерева k можно распознать и построить для них дерево разложения ширины k за линейное время. Временная зависимость этого алгоритма от k экспоненциальна. Ввиду важной роли ширины дерева в огромном количестве областей, было разработано множество практических и теоретических алгоритмов для вычисления ширины дерева графа. В зависимости от конкретной задачи, может быть предпочтительнее лучшее соотношение аппроксимации или лучшая зависимость времени работы от размера входных данных или ширины дерева. Ниже представлена таблица с обзором некоторых алгоритмов для вычисления ширины дерева. Здесь k – ширина дерева, а n – количество вершин входного графа G. Каждый из алгоритмов за время f(k) ⋅ g(n) выдает разложение ширины, указанное в столбце "Аппроксимация". Например, алгоритм за время либо строит дерево разложения входного графа G шириной не более k, либо сообщает, что ширина дерева G больше k. Аналогично, алгоритм за время либо строит дерево разложения входного графа G шириной не более 5k + 4, либо сообщает, что ширина дерева G больше k. улучшил этот результат до 2k + 1 за то же время работы. Аппроксимация f(k) g(n) ссылка точная O(1) 4k + 3 8k + 7 5k + 4 (или 7k + 6) n log n точная O(n) O(1) 4.5k + 4 точная O(1) 3k + 2 O(n log n) 5k + 4 O(n) O(n log n) 5k + 4 O(n log n) 2k + 1O(n) 5k + 4 O(n log n) точная (1+)k

Неизвестно, является ли определение ширины дерева планарных графов NP-полной задачей, или их ширину дерева можно вычислить за полиномиальное время. На практике алгоритм может определять ширину дерева графов с числом вершин до 100 и шириной дерева до 11, находя хордальное завершение этих графов с оптимальной шириной дерева. Для больших графов можно использовать методы поиска, такие как поиск с отсечениями (BnB) и поиск в ширину, для вычисления ширины дерева. Эти алгоритмы являются алгоритмами с прерыванием, то есть при ранней остановке они выдают верхнюю границу для ширины дерева. Первый алгоритм BnB для вычисления ширины дерева, названный QuickBB, был предложен Гогате и Дехтером. Поскольку качество любого алгоритма BnB сильно зависит от качества используемой нижней оценки, Гогате и Дехтер улучшили алгоритм QuickBB, используя поиск в ширину. На некоторых графах этот алгоритм поиска в ширину работает на порядок быстрее, чем QuickBB.

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

В начале 1970-х годов было замечено, что большой класс комбинаторных задач оптимизации, определенных на графах, может быть эффективно решен с помощью несерийного динамического программирования, если граф имеет ограниченную размерность – параметр, который впоследствии был показан эквивалентным древовидной ширине. Позже, в конце 1980-х годов, несколько авторов независимо друг от друга обнаружили, что многие алгоритмические задачи, являющиеся NP-полными для произвольных графов, могут быть эффективно решены динамическим программированием для графов с ограниченной древовидной шириной, используя древовидные декомпозиции этих графов. Например, задача раскраски графа с древовидной шириной k может быть решена с помощью алгоритма динамического программирования на древовидной декомпозиции графа. Для каждого мешка древовидной декомпозиции и каждого разбиения вершин этого мешка на цветовые классы алгоритм определяет, является ли данная раскраска допустимой и может ли она быть расширена на все дочерние узлы в древовидной декомпозиции, объединяя информацию аналогичного типа, вычисленную и сохраненную в этих узлах. В результате, оптимальная раскраска графа с n вершинами находится за время O(k^(k+O(1))n), что делает эту задачу фиксированно-параметрически разрешимой.

Ширина пути

Ширина пути графа имеет очень похожее определение на ширину дерева через дерево разложения, но ограничивается деревьями разложения, в которых базовое дерево разложения является графом-путем. Альтернативно, ширину пути можно определить на основе интервальных графов аналогично определению ширины дерева на основе хордальных графов. Как следствие, ширина пути графа всегда не меньше его ширины дерева, но может быть больше лишь на логарифмический фактор. Лучшие известные границы для f таковы: f должно быть не меньше Ω(r^d) для некоторой фиксированной константы d > 0, и не больше…

Для пояснения обозначения Ω в нижней границе см. статью о нотации «большое O». Более точные границы известны для ограниченных семейств графов, что позволяет разрабатывать эффективные алгоритмы для многих задач оптимизации графов в этих семействах, используя теорию двумерности. Теорема Халина о решетке предоставляет аналогию связи между шириной дерева и размером решетчатой минорной структуры для бесконечных графов.

Диаметр и местная ширина дерева

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

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

определяет класс параметров графа, которые он называет S-функциями, включающими ширину дерева. Эти функции, отображающие графы в целые числа, должны быть равны нулю для графов без ребер, быть минор-монотонными (функция f называется "минор-монотонной", если для любого минора H графа G выполняется f(H) ≤ f(G)), увеличиваться на единицу при добавлении новой вершины, смежной со всеми предыдущими, и принимать большее значение из двух подграфов, разделенных кликовым сепаратором. Множество всех таких функций образует полную решетку относительно операций поточечного минимума и максимума. Наибольшим элементом в этой решетке является ширина дерева, а наименьшим – число Хадвигера, равное размеру наибольшего полного минора в заданном графе.