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

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

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

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

Определение

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

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

Объединение всех множеств $X i$ равно $V$ . То есть каждая вершина графа связана как минимум с одним узлом дерева.
Для каждого ребра $(v, w)$ в графе существует подмножество $X i,$ содержащее как $v,$ так и $w$ . То есть вершины смежны в графе только тогда, когда соответствующие поддеревья имеют общий узел.
Если $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$ , то $X_{i}\cap X_{j}\subseteq X_{k}$ .

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

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

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

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

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

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

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

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

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

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

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

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

где сумма при расчете $A(S,i)$ находится над дочерними элементами узла $X i$ .

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

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

См. также

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

Примечания

^ Готтлоб и др. (2012) .
^ Дистель (2005), стр. 354–355.
^ Дистель (2005), раздел 12.3
^ Jump up to: ^а ^б ^с Бодлендер (1996) .
^ Арнборг, Корнейл и Проскуровски (1987) .
^ Бертеле и Бриоски (1972) .
^ Арнборг и Проскуровски (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 .
Берн, МВт; Лоулер, Эл . ; Вонг, AL (1987), «Вычисление оптимальных подграфов разложимых графов в линейном времени», Journal of Algorithms , 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 .
Готтлоб, Георг; Ли, Стефани Тьен; Валиант, Грегори; Валиант, Пол (2012), «Границы размера и ширины дерева для конъюнктивных запросов», Журнал ACM , 59 (3): A16:1–A16:35, doi : 10.1145/2220357.2220363 , MR 2946220
Халин, Рудольф (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 .

[FOOTNOTEGottlobLeeValiantValiant2012-1] Готтлоб и др. (2012) .

[2] Дистель (2005), стр. 354–355.

[3] Дистель (2005), раздел 12.3

[b96-4] Jump up to: ^а ^б ^с Бодлендер (1996) .

[5] Арнборг, Корнейл и Проскуровски (1987) .

[FOOTNOTEBerteléBrioschi1972-6] Бертеле и Бриоски (1972) .

[7] Арнборг и Проскуровски (1989) ; Берн, Лоулер и Вонг (1987) ; Бодлендер (1988) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]