Разложение дерева

Преобразование графа в дерево

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

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

Древовидные декомпозиции также называются деревьями соединений , деревьями клик или деревьями соединений . Они играют важную роль в таких задачах, как вероятностный вывод , удовлетворение ограничений , оптимизация запросов ^{и разложение матрицы} .

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

Определение

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

Каждое поддерево связывает вершину графа с набором узлов дерева. Чтобы определить это формально, мы представляем каждый узел дерева как набор связанных с ним вершин. Таким образом, для данного графа G = ( V , E ) разложение дерева — это пара ( X , T ) , где X = { X1 _, …, Xn _} — семейство подмножеств (иногда называемых мешками ) графа V , и T — дерево, узлами которого являются подмножества X _i , удовлетворяющие следующим свойствам: ^[2]

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

Древовидная декомпозиция графа далеко не уникальна; например, тривиальное разложение дерева содержит все вершины графа в одном корневом узле.

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

Древовидное разложение ( X , T = ( I , F )) дерева ширины k является гладким , если для всех и для всех . ^[3] ${\displaystyle i\in I:|X_{i}|=k+1}$ ${\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}$

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

Два разных древовидных разложения одного и того же графа

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

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

Динамическое программирование

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

В качестве примера рассмотрим задачу нахождения максимального независимого множества в графе ширины дерева k . Чтобы решить эту проблему, сначала произвольно выберите один из узлов разложения дерева в качестве корня. Для узла X _i древесного разложения пусть D _i будет объединением множеств X _j , спускающихся из X _i . Для независимого набора пусть A ( S , i ) обозначает размер наибольшего независимого подмножества _I из Di такого , что Аналогично, для соседней пары узлов X _i и X _j , причем X _i находится дальше от корня дерева, чем X _j и независимый набор, пусть B ( S , i , j ) обозначают размер наибольшего независимого подмножества I из D _i , такого, что мы можем вычислить эти значения A и B путем обхода дерева снизу вверх: ${\displaystyle S\subset X_{i},}$ ${\displaystyle I\cap X_{i}=S.}$ ${\displaystyle S\subset X_{i}\cap X_{j},}$ ${\displaystyle I\cap X_{i}\cap X_{j}=S.}$

${\displaystyle A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)}$

${\displaystyle B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)}$

где сумма при вычислении относится к дочерним элементам узла X _i . ${\displaystyle A(S,i)}$

В каждом узле или ребре существует не более 2 ^k наборов S , для которых нам нужно вычислить эти значения, поэтому, если k является константой, то весь расчет занимает постоянное время для каждого ребра или узла. Размер максимального независимого набора — это наибольшее значение, хранящееся в корневом узле, а сам максимальный независимый набор можно найти (как это стандартно в алгоритмах динамического программирования) путем обратного поиска по этим сохраненным значениям, начиная с этого самого большого значения. Таким образом, в графах ограниченной древовидной ширины задача о максимальном независимом множестве может быть решена за линейное время. Подобные алгоритмы применимы и ко многим другим задачам с графами.

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

Смотрите также

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

Примечания

1. Дистель (2005), стр. 354–355.
2. Дистель (2005), раздел 12.3
3. Бодлендер (1996).
4. Арнборг, Корней и Проскуровски (1987).
5. Бертеле и Бриоски (1972).
6. Арнборг и Проскуровски (1989); Берн, Лоулер и Вонг (1987); Бодлендер (1988).

Рекомендации

• Арнборг, С.; Корней, Д. ; Проскуровски, А. (1987), «Сложность поиска вложений в k -дереве», SIAM Journal on Matrix Analysis and Applications , 8 (2): 277–284, doi : 10.1137/0608024.
• Арнборг, С.; Проскуровски, А. (1989), «Алгоритмы с линейным временем для NP-трудных задач, ограниченных частичными k -деревьями», Discrete Applied Mathematics , 23 (1): 11–24, doi : 10.1016/0166-218X(89)90031- 0.
• Берн, МВт; Лоулер, Эл . ; Вонг, А.Л. (1987), «Вычисление оптимальных подграфов разложимых графов в линейном времени», Журнал алгоритмов , 8 (2): 216–235, doi : 10.1016/0196-6774(87)90039-3.
• Бертеле, Умберто; Бриоски, Франческо (1972), Непоследовательное динамическое программирование , Academic Press, ISBN 0-12-093450-7.
• Бодлендер, Ханс Л. (1988), «Динамическое программирование на графах с ограниченной шириной дерева», Proc. 15-й Международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике, том. 317, Springer-Verlag, стр. 105–118, doi : 10.1007/3-540-19488-6_110, hdl : 1874/16258.
• Бодлендер, Ханс Л. (1996), «Алгоритм с линейным временем для поиска разложений деревьев небольшой ширины», SIAM Journal on Computing , 25 (6): 1305–1317, CiteSeerX  10.1.1.113.4539 , doi : 10.1137/S0097539793251219.
• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6.
• Халин, Рудольф (1976), « S -функции для графов», Journal of Geometry , 8 (1–2): 171–186, doi : 10.1007/BF01917434, S2CID  120256194.
• Робертсон, Нил ; Сеймур, Пол Д. (1984), «Минорные графы III: ширина плоского дерева», Журнал комбинаторной теории , серия B, 36 (1): 49–64, doi : 10.1016/0095-8956(84)90013-3.