Ширина дерева

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

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

Концепция ширины дерева была первоначально введена Умберто Бертеле и Франческо Бриоски ( 1972 ) под названием « размер» . Позже он был переоткрыт Рудольфом Халином  ( 1976 ) на основе свойств, которые он разделяет с другим параметром графа, числом Хадвигера . Позже он был снова открыт Нилом Робертсоном и Полом Сеймуром  ( 1984 ) и с тех пор изучается многими другими авторами. ^[1]

Определение [ править ]

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

Разложение дерева графа G = ( V , E ) является деревом, Т , с узлами Х ₁ , ..., Х _п , где каждый Х _я есть подмножество V , удовлетворяющее следующие свойства ^[2] (в термин узел используется для обозначения вершины T, чтобы избежать путаницы с вершинами G ):

1. Объединение всех множеств X _я равен V . То есть каждая вершина графа содержится как минимум в одном узле дерева.
2. Если X _i и X _j оба содержат вершину v , то все узлы X _k из T на (уникальном) пути между X _i и X _{j также} содержат v . Эквивалентно, узлы дерева , содержащие вершину V образуют связное поддерево T .
3. Для каждого ребра ( v , w ) в графе существует подмножество X _i, которое содержит как v, так и w . То есть вершины смежны в графе только тогда, когда соответствующие поддеревья имеют общий узел.

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

Эквивалентно, ширина дерева G на единицу меньше размера самой большой клики в хордальном графе, содержащем G с наименьшим номером клики . Хордовый граф с таким размером клики может быть получен добавлением к G ребра между каждыми двумя вершинами, которые обе принадлежат хотя бы одному из множеств X _i .

Treewidth также можно охарактеризовать в терминах убежищ , функций, описывающих стратегию уклонения для определенной игры преследования-уклонения, определенной на графе. Граф G имеет ширину дерева k тогда и только тогда, когда он имеет убежище порядка k + 1, но не более высокого порядка, где убежище порядка k + 1 - это функция β, которая отображает каждое множество X из не более чем k вершин в G в одна из компонент связности группы G \ X , обладающая свойством монотонности, что β ( Y) ⊆ & beta ; ( Х ) всякий раз , когда X ⊆ Y .

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

Примеры [ править ]

Каждый полный граф K _n имеет ширину дерева n  - 1. Это легче всего увидеть, используя определение ширины дерева в терминах хордовых графов: полный граф уже является хордовым, и добавление дополнительных ребер не может уменьшить размер его наибольшей клики.

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

Ограниченная ширина дерева [ править ]

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

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

В плоских графах не имеют ограниченную древесную ширину, поскольку п × п решетчатый граф является планарным графом с древесной шириной точно п . Следовательно, если F - семейство минорно-замкнутых графов с ограниченной шириной дерева, оно не может включать все плоские графы. И наоборот, если некоторый планарный граф не может быть второстепенным для графов семейства F , тогда существует константа k такая, что все графы в F имеют ширину дерева не более k . То есть следующие три условия эквивалентны друг другу: ^[6]

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

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

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

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

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

Алгоритмы [ править ]

Вычисление ширины дерева [ править ]

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

Из-за роли, которую ширина дерева играет в огромном количестве полей, были разработаны различные практические и теоретические алгоритмы вычисления ширины дерева графа. В зависимости от используемого приложения можно предпочесть лучший коэффициент аппроксимации или лучшую зависимость времени выполнения от размера ввода или ширины дерева. В таблице ниже представлен обзор некоторых алгоритмов ширины дерева. Вот ширина дерева и количество вершин входного графа . Каждый из алгоритмов выводит по времени разложение ширины, указанной в столбце Приближение. Например, алгоритм Бодлендера (1996) во времени либо строит древовидное разложение входного графа шириной не более ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle G}$${\ Displaystyle е (к) \ CDOT г (п)}$${\ Displaystyle О (к ^ {О (к ^ {3})}) \ CDOT п}$${\ displaystyle G}$${\ displaystyle k}$или сообщает, что ширина дерева больше чем . Аналогичным образом алгоритм Bodlaender et al. (2016) со временем либо строит древовидную декомпозицию входного графа шириной не более, либо сообщает, что ширина дерева больше, чем . ${\ displaystyle G}$${\ displaystyle k}$${\ Displaystyle 2 ^ {О (к)} \ cdot п}$${\ displaystyle G}$${\ displaystyle 5k + 4}$${\ displaystyle G}$${\ displaystyle k}$

Приближение	f (k)	г (п)	ссылка
точный	${\ displaystyle O (1)}$	${\ Displaystyle О (п ^ {к + 2})}$	Арнборг, Корнейл и Проскуровски (1987)
${\ displaystyle 4k + 3}$	${\ displaystyle O (3 ^ {3k})}$	${\displaystyle O(n^{2})}$	Робертсон и Сеймур (1995)
точный	${\displaystyle k^{O(k^{3})}}$	${\displaystyle O(n)}$	Бодлендер (1996)
${\displaystyle O(k\cdot {\sqrt {\log k}})}$	${\displaystyle O(1)}$	${\displaystyle n^{O(1)}}$	Файги, Хаджиагайи и Ли (2008)
точный	${\displaystyle O(1)}$	${\displaystyle O(1.7347^{n})}$	Фомин, Тодинка и Вилланджер (2015)
${\displaystyle 5k+4}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	Bodlaender et al. (2016)
${\displaystyle k^{2}}$	${\displaystyle O(k^{7})}$	${\displaystyle O(n\log n)}$	Фомин и др. (2018)

Неизвестно, является ли определение ширины дерева планарных графов NP-полным, или их ширина дерева может быть вычислена за полиномиальное время. ^[13]

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

Решение других задач на графиках малой ширины дерева [ править ]

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

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

Теорема Курселя [ править ]

Для большого класса задач существует алгоритм линейного времени для решения задачи из класса, если предусмотрено дерево-разложение с постоянной ограниченной шириной дерева . В частности, теорема Курселя ^{[16] [17]} утверждает, что если проблема графа может быть выражена в логике графов с использованием монадической логики второго порядка , то она может быть решена за линейное время на графах с ограниченной шириной дерева. Monadic логика второго порядка является языком для описания свойств графов , которые используются следующими конструкции: логические операции ( ), членство тесты (например, ), количественные над вершинами, ребра, множество вершин, множество ребер (например, , , , ${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$${\displaystyle e\in E,v\in V}$${\displaystyle \forall }$ ${\displaystyle v\in V}$${\displaystyle \exists }$ ${\displaystyle e\in E}$${\displaystyle \exists }$ ${\displaystyle I\subseteq V}$${\displaystyle \forall }$ ${\displaystyle F\subseteq E}$), тесты смежности ( u - конечная точка e ) и некоторые расширения, которые позволяют выполнять такие операции, как оптимизация.

Рассмотрим, например, задачу 3-раскраски графов. Для графа эта задача спрашивает, можно ли присвоить каждой вершине один из трех цветов, чтобы никаким двум смежным вершинам не был назначен один и тот же цвет. Эта проблема может быть выражена в монадической логике второго порядка следующим образом: ${\displaystyle G=(V,E)}$${\displaystyle v\in V}$

${\displaystyle \exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge }$

${\displaystyle \forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))}$,

где представляют собой подмножества вершин каждого из трех цветов. Следовательно, согласно результатам Курселя, проблема 3-раскраски может быть решена за линейное время для графа, заданного древовидным разложением с ограниченной постоянной шириной дерева.${\displaystyle W_{1},W_{2},W_{3}}$

Связанные параметры [ править ]

Пропускная способность [ править ]

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

Малый размер сетки [ править ]

Поскольку древесная ширина из п  ×  п сеточного графа является п , то древесная ширина графа G всегда больше или равен размеру самого большого квадрата сетки минор из G . В другом направлении, то теорема сетки незначительные по Robertson и Seymour показывает , что существует функция ф такая , что древесная ширина составляет не более е ( г ) , где г является размер самого большого квадрата сетки минор. ^[18] Наилучшие оценки, известные на f, заключаются в том, что fдолжно быть не меньше Ω ( r ^d ) для некоторой фиксированной константы d > 0 и не больше O ( √ r / log r ). ^[19] Более точные границы известны для семейств ограниченных графов, что приводит к эффективным алгоритмам для многих задач оптимизации графов для этих семейств с помощью теории двумерности . ^[20] Сеточная теорема Халина обеспечивает аналог отношения между шириной дерева и второстепенным размером сетки для бесконечных графов. ^[21]

Диаметр и местная ширина дерева [ править ]

Семейство F графов, замкнутое относительно взятия подграфов, называется ограниченной локальной шириной дерева или свойством диаметра-дерева , если ширина дерева графов в семействе ограничена сверху функцией их диаметра . Если класс также предполагается замкнутым относительно взятия миноров , то F имеет ограниченную локальную ширину дерева тогда и только тогда, когда один из запрещенных миноров для F является вершинным графом . ^[22] Первоначальные доказательства этого результата показали, что ширина дерева в семействе графов без апекс-миноров растет не более чем вдвое экспоненциально как функция диаметра;^[23] позже это было сведено к однократной экспоненциальной ^[20] и, наконец, к линейной оценке. ^[24] Ограниченность местная древесная ширина тесно связана с алгоритмической теорией bidimensionality , ^[25] , и каждый граф свойство определимы в логике первого порядка может быть решен за апекс-минор свободного граф семьи в количестве временикоторое лишь слегка сверхлинейный . ^[26]

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

Число Хадвигера и S- функции [ править ]

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

Заметки [ править ]

Ссылки [ править ]