Разложение дерева

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

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

Разложения дерева также называют клеммные деревья , кружковыми деревья , или присоединиться к деревьям ; они играют важную роль в таких проблемах, как вероятностный вывод , удовлетворение ограничений , оптимизация запросов , ^{[ необходима цитата ]} и разложение матриц .

Концепция разложения дерева была первоначально введена Рудольфом Халином  ( 1976 ). Позже он был переоткрыт Нилом Робертсоном и Полом Сеймуром  ( 1984 ) и с тех пор изучается многими другими авторами. ^[1]

Определение [ править ]

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

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

1. Объединение всех множеств X _я равен 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} \ substeq X_ {k}}$

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

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

Разложение дерева ( Х , Т = ( I , F )) от древесной ширины к является гладким , если для всех , и для всех . ^[3]${\displaystyle i\in I:|X_{i}|=k+1}$${\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k}$

Минимальное количество деревьев в разложении дерева является дерево число из G.

Treewidth [ править ]

Два разных древовидных разложения одного и того же графа

Ширина из разложения дерева является размер ее наибольшего множества X _I минус один. Древесная ширина TW ( G ) графа G является минимальная ширина среди всех возможных разбиений дерева из G . В этом определении размер самого большого набора уменьшается на единицу, чтобы сделать ширину дерева равной единице. Ширина дерева также может быть определена из структур, отличных от древовидной декомпозиции, включая хордовые графы , ежевики и убежища .

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

Динамическое программирование [ править ]

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

В качестве примера рассмотрим задачу поиска максимального независимого множества в графе ширины дерева k . Чтобы решить эту проблему, сначала произвольно выберите один из узлов разложения дерева в качестве корня. Для узла X _i разложения дерева пусть D _i будет объединением множеств X _j, спускающихся из X _i . Для независимого множества S  ⊂  X _i через A ( S , i ) обозначим размер наибольшего независимого подмножества I в D _i такого, что I ∩  X _я  =  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 является константой, то все вычисления занимают постоянное время для каждого ребра или узла. Размер максимального независимого набора - это наибольшее значение, хранящееся в корневом узле, а сам максимальный независимый набор может быть найден (как стандарт в алгоритмах динамического программирования) путем обратного отслеживания этих сохраненных значений, начиная с этого наибольшего значения. Таким образом, в графах с ограниченной шириной дерева задача о максимальном независимом множестве может быть решена за линейное время. Подобные алгоритмы применимы ко многим другим задачам с графами.

Этот подход динамического программирования используется в машинном обучении через алгоритм дерева соединений для распространения убеждений в графах с ограниченной шириной дерева . Он также играет ключевую роль в алгоритмах для вычисления ширины дерева и построения разложения дерева: обычно такие алгоритмы имеют первый шаг, который аппроксимирует ширину дерева, построение разложения дерева с этой приблизительной шириной, а затем второй шаг, который выполняет динамическое программирование в приблизительное разложение дерева для вычисления точного значения ширины дерева. ^[3]

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]