Loading AI tools
отображение графа в дерево Из Википедии, свободной энциклопедии
В теории графов древесная декомпозиция — это отображение графа в дерево, которое может быть использовано для определения древесной ширины графа и ускорения решения определённых вычислительных задач на графах.
В области машинного обучения древесная декомпозиция называется также деревом сочленений, деревом клик или деревом смежности. Древесная декомпозиция играет важную роль в задачах, подобных вероятностному логическому выводу, поиску допустимых значений[англ.], оптимизации запросов СУБД и разложения матриц.
Понятие древесной декомпозиции было первоначально предложено Халином[1]. Позднее его переоткрыли Робертсон и Сеймур[2] и с тех пор понятие изучалось многими другими авторами[3].
Интуитивно древесная декомпозиция представляет вершины заданного графа G как поддеревья дерева таким образом, что вершины графа смежны только тогда, когда соответствующие поддеревья пересекаются. Тогда G образует подграф графа пересечений поддеревьев. Полный граф пересечений — это хордальный граф.
Каждое поддерево связывает вершину графа с множеством узлов дерева. Чтобы определить это формально, мы представим каждый узел дерева как множество вершин, связанных с ней. Тогда для заданного графа G = (V, E) древесная декомпозиция — это пара (X, T), где X = {X1, ..., Xn} является семейством подмножеств множества V, а T является деревом, узлами которого служат подмножества Xi, удовлетворяющие следующим свойствам: [4]
Древесная декомпозиция графа далеко не уникальна. Например, тривиальная древесная декомпозиция содержит все вершины графа в корневом узле.
Древесная декомпозиция, в которой деревом служит путь, называется путевой декомпозицией и древесная ширина этого специального вида древесной декомпозиции известна как путевая ширина.
Древесная декомпозиция (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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
