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

Отображение графа в дерево

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

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

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

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

Определение

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

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

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 является гладкой , если для всех и для всех . ^[4] ${\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 . ^[5] Однако, когда k — любая фиксированная константа, графы с древовидной шириной k могут быть распознаны, и для них может быть построена древовидная декомпозиция ширины k за линейное время. ^[4] Зависимость этого алгоритма от времени k является экспоненциальной функцией k ³ .

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

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

В качестве примера рассмотрим задачу поиска максимального независимого множества в графе с древовидной шириной k . Чтобы решить эту задачу, сначала произвольно выберем один из узлов разложения дерева в качестве корня. Для узла X _i разложения дерева пусть D _i будет объединением множеств X _{j ,} нисходящих от X _i . Для независимого множества пусть A ( S , i ) обозначает размер наибольшего независимого подмножества I из D _i такого, что Аналогично для смежной пары узлов 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 является константой, то все вычисление занимает постоянное время на ребро или узел. Размер максимального независимого множества — это наибольшее значение, хранящееся в корневом узле, а само максимальное независимое множество может быть найдено (как это стандартно в алгоритмах динамического программирования) путем возврата по этим хранимым значениям, начиная с этого наибольшего значения. Таким образом, в графах ограниченной ширины дерева задача максимального независимого множества может быть решена за линейное время. Аналогичные алгоритмы применимы ко многим другим задачам графов.

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

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

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

Примечания

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

Ссылки

• Арнборг, С.; Корнейл, Д .; Проскуровски, А. (1987), «Сложность поиска вложений в k -дереве», Журнал SIAM по матричному анализу и приложениям , 8 (2): 277–284, doi :10.1137/0608024.
• Арнборг, С.; Проскуровски, А. (1989), «Линейные алгоритмы для NP-трудных задач, ограниченных частичными k- деревьями», Дискретная прикладная математика , 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.
• Bodlaender, Hans L. (1988), "Динамическое программирование на графах с ограниченной древовидной шириной", Proc. 15th International Colloquium on Automata, Languages ​​and Programming , Lecture Notes in Computer Science, т. 317, Springer-Verlag, стр. 105–118, doi :10.1007/3-540-19488-6_110, hdl : 1874/16258 , ISBN 978-3-540-19488-0.
• Бодлендер, Ханс Л. (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 -функции для графов», Журнал геометрии , 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.