Введение
Отображение графа в дерево, древовидная структура графов.
tree structure of graphs
В теории графов, дерево декомпозиции — это отображение графа в дерево, которое может быть использовано для определения древовидности графа и ускорения решения определенных вычислительных задач на графе. Деревья декомпозиции также называются деревьями соединений, деревьями клик или объединительными деревьями. Они играют важную роль в задачах, таких как вероятностный вывод, задача об удовлетворимости ограничений, оптимизация запросов и разложение матриц. Концепция дерева декомпозиции была первоначально введена, а затем повторно открыта и с тех пор изучалась многими другими авторами.
Ширина дерева
Ширина разложения дерева равна размеру его наибольшего множества минус один. Древесная ширина tw(G) графа G — это минимальная ширина среди всех возможных разложений дерева для G. В этом определении размер наибольшего множества уменьшается на единицу, чтобы древесная ширина дерева была равна одному. Древесную ширину можно также определить на основе других структур, отличных от разложений дерева, включая хордальные графы, brambles и havens. Определение того, имеет ли данный граф G древесную ширину не более заданной величины k, является NP-полной задачей. Однако, если k — фиксированная константа, графы с древесной шириной k можно распознать и построить для них дерево разложения ширины k за линейное время. Многие алгоритмические задачи, NP-полные для произвольных графов, могут быть эффективно решены с помощью динамического программирования для графов с ограниченной древесной шириной, используя разложения дерева этих графов. В качестве примера рассмотрим задачу нахождения максимального независимого множества в графе с древесной шириной k. Чтобы решить эту задачу, сначала произвольно выберите один из узлов разложения дерева в качестве корня. Для узла разложения дерева пусть S будет объединением множеств, нисходящих от него. Для независимого множества пусть A(S, i) обозначает размер наибольшего независимого подмножества I из S, такого что I ⊆ S. Аналогично, для пары смежных узлов i и j, где j находится дальше от корня дерева, чем i, и независимого множества пусть B(S, i, j) обозначает размер наибольшего независимого подмножества I из S, такого что I ⊆ S. Мы можем вычислить эти значения A и B, проходя по дереву снизу вверх:
However, when k is any fixed constant, the graphs with treewidth k can be recognized, and a width k tree decomposition constructed for them, in linear time. that many algorithmic problems that are NP complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree decompositions of these graphs. As an example, consider the problem of finding the maximum independent set in a graph of treewidth k. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node of the tree decomposition, let be the union of the sets descending from For an independent set let A(S,i) denote the size of the largest independent subset I of such that Similarly, for an adjacent pair of nodes and , with farther from the root of the tree than , and an independent set let B(S,i,j) denote the size of the largest independent subset I of such that We may calculate these A and B values by a bottom up traversal of the tree:
где сумма в вычислении A(S, i) берется по всем дочерним узлам узла i.
На каждом узле или ребре необходимо вычислить значения для не более k множеств S, поэтому, если k — константа, все вычисления занимают постоянное время на ребро или узел. Размер максимального независимого множества — это наибольшее значение, хранящееся в корневом узле, а само максимальное независимое множество можно найти (как это обычно делается в алгоритмах динамического программирования) путем обратного прохода по этим сохраненным значениям, начиная с этого наибольшего значения. Таким образом, в графах с ограниченной древесной шириной задача максимального независимого множества может быть решена за линейное время. Подобные алгоритмы применимы ко многим другим задачам теории графов. Этот подход динамического программирования используется в машинном обучении через алгоритм дерева соединений для распространения убеждений в графах с ограниченной древесной шириной. Он также играет ключевую роль в алгоритмах для вычисления древесной ширины и построения разложений дерева: обычно такие алгоритмы состоят из первого шага, который приближает древесную ширину, строя разложение дерева с этой приблизительной шириной, и второго шага, который выполняет динамическое программирование в приблизительном разложении дерева для вычисления точного значения древесной ширины.
At each node or edge, there are at most sets S for which we need to calculate these values, so if k is a constant then the whole calculation takes constant time per edge or node. The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value. Thus, in graphs of bounded treewidth, the maximum independent set problem may be solved in linear time. Similar algorithms apply to many other graph problems. This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth. It also plays a key role in algorithms for computing the treewidth and constructing tree decompositions: typically, such algorithms have a first step that approximates the treewidth, constructing a tree decomposition with this approximate width, and then a second step that performs dynamic programming in the approximate tree decomposition to compute the exact value of the treewidth.