Древесная декомпозиция

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

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

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

Понятие древесной декомпозиции было первоначально предложено Халином^[1]. Позднее его переоткрыли Робертсон и Сеймур^[2] и с тех пор понятие изучалось многими другими авторами^[3].

Определение

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

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

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. Это свойство можно сформулировать эквивалентно — если ${\displaystyle X_{i}}$, ${\displaystyle X_{j}}$ и ${\displaystyle X_{k}}$ являются узлами, а ${\displaystyle X_{k}}$ находится на пути из ${\displaystyle X_{i}}$ в ${\displaystyle X_{j}}$, то ${\displaystyle X_{i}\cap X_{j}\subseteq X_{k}}$.

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

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

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

Древесная ширина

Основная статья: Древесная ширина (теория графов)

Две различные древесные декомпозиции одного графа

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

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

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

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

В качестве примера представим себе задачу поиска наибольшего независимого множества на графе с древесной шириной k. Для решения этой задачи сначала выберем один узел древесного разложения в качестве корня (произвольным образом). Для узла X_i древесной декомпозиции пусть D_i будет объединением множеств X_j, наследуемых от X_i. Для независимого множества S ⊂ X_i пусть A(S,i) означает размер наибольшего независимого подмножества I в D_i, такого, что I ∩ X_i = S. Подобным образом для смежной пары узлов X_i и X_j с X_i более дальним от корня по сравнению с X_j и независимого множества S ⊂ X_i ∩ X_j пусть B(S,i,j) означает размер наибольшего независимого подмножества I в D_i, такого, что I ∩ X_i ∩ X_j = S. Мы можем вычислить эти значения A и B проходом дерева снизу вверх:

${\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)}$

Где сумма в формуле для ${\displaystyle A(S,i)}$ берётся по потомкам узла ${\displaystyle X_{i}}$.

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

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

См. также

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

Примечания

1. Halin, 1976.
2. Robertson, Seymour, 1984.
3. Diestel, 2005, с. 354–355.
4. Diestel, 2005, с. section 12.3.
5. Bodlaender, 1996.
6. Arnborg, Corneil, Proskurowski, 1987.
7. Bertelé, Brioschi, 1972.
8. Arnborg, Proskurowski, 1989; Bern, Lawler, Wong, 1987; Bodlaender, 1988.

Литература

• S. Arnborg, D. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree // SIAM Journal on Matrix Analysis and Applications. — 1987. — Т. 8, вып. 2. — С. 277–284. — doi:10.1137/0608024..
• S. Arnborg, A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Applied Mathematics. — 1989. — Т. 23, вып. 1. — С. 11–24. — doi:10.1016/0166-218X(89)90031-0..
• M. W. Bern, E. L. Lawler, A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs // Journal of Algorithms. — 1987. — Т. 8, вып. 2. — С. 216–235. — doi:10.1016/0196-6774(87)90039-3..
• Umberto Bertelé, Francesco Brioschi. Nonserial Dynamic Programming. — Academic Press, 1972. — ISBN 0-12-093450-7..
• Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317. — С. 105–118. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-19488-6_110..
• Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth // SIAM Journal on Computing. — 1996. — Т. 25, вып. 6. — С. 1305–1317. — doi:10.1137/S0097539793251219..
• Reinhard Diestel. Graph Theory. — 3rd. — Springer, 2005. — ISBN 3-540-26182-6..
• Rudolf Halin. S-functions for graphs // Journal of Geometry. — 1976. — Т. 8. — С. 171–186. — doi:10.1007/BF01917434..
• Neil Robertson, Paul D. Seymour. Graph minors III: Planar tree-width // Journal of Combinatorial Theory, Series B. — 1984. — Т. 36, вып. 1. — С. 49–64. — doi:10.1016/0095-8956(84)90013-3..