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

Интуитивно древесная декомпозиция представляет вершины заданного графа 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].

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