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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

В начале 1970-х было замечено, что задачи из большого класса комбинаторных оптимизационных задач на графах могут быть эффективно решены с помощью несериального динамического программирования, если граф имеет ограниченную размерность[7], связанный с древесной шириной параметр. Позднее некоторые авторы независимо обнаружили к концу 1980-х [8], что многие алгоритмические 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 является константой, все вычисления занимают постоянное время на одно ребро или узел. Размер наибольшего независимого множества является наибольшим значением, запомненном в корневом узле, а само наибольшее независимое множество можно найти (что является стандартным для динамического программирования) путём отслеживания в обратном порядке этих запомненных значений, начиная с наибольшего значения. Таким образом, в графах ограниченной древесной ширины задача поиска наибольшего независимого множества может быть решена за линейное время. Подобные алгоритмы применимы для многих других задач на графах.

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

См. также

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

Примечания

Литература

  • 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..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.