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

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

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

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

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

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

Объединение всех множеств Xi равно V. Таким образом, любая вершина графа связана хотя бы с одним узлом дерева. Для любого ребра (v, w) графа существует подмножество Xi, содержащее как v, так и w. Таким образом, вершины смежны в графе, если только они соответствуют поддеревьям, имеющим общий узел. Если Xi и Xj содержат вершину v, то все узлы Xk дерева в (уникальном) пути между Xi и Xj содержат v тоже. То есть узлы, связанные с вершиной v, образуют связное подмножество в T. Это свойство можно сформулировать эквивалентно — если , и являются узлами, а находится на пути из в , то .

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

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

Древовидная декомпозиция (X, T = (I, F)) с древовидной шириной k является гладкой, если для всех и для всех .

Древовидная ширина

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

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

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

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

Где сумма в формуле для берётся по потомкам узла .

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

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

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

Примечания

Литература

. . . . . . . . .

Категория:Деревья (графы) Категория:Теория миноров графов Категория:Объекты теории графов