Как найти ширину дерева

From Wikipedia, the free encyclopedia

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms. Many algorithms that are NP-hard for general graphs, become easier when the treewidth is bounded by a constant.

The concept of treewidth was originally introduced by Umberto Bertelè and Francesco Brioschi (1972) under the name of dimension. It was later rediscovered by Rudolf Halin (1976), based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by Neil Robertson and Paul Seymour (1984) and has since been studied by many other authors.^[1]

Definition[edit]

A tree decomposition of a graph G = (V, E) is a tree T with nodes X₁, …, X_n, where each X_i is a subset of V, satisfying the following properties^[2] (the term node is used to refer to a vertex of T to avoid confusion with vertices of G):

1. The union of all sets X_i equals V. That is, each graph vertex is contained in at least one tree node.
2. If X_i and X_j both contain a vertex v, then all nodes X_k of T in the (unique) path between X_i and X_j contain v as well. Equivalently, the tree nodes containing vertex v form a connected subtree of T.
3. For every edge (v, w) in the graph, there is a subset X_i that contains both v and w. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.

The width of a tree decomposition is the size of its largest set X_i minus one. The treewidth tw(G) of a graph G is the minimum width among all possible tree decompositions of G. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.

Equivalently, the treewidth of G is one less than the size of the largest clique in the chordal graph containing G with the smallest clique number. A chordal graph with this clique size may be obtained by adding to G an edge between every two vertices that both belong to at least one of the sets X_i.

Treewidth may also be characterized in terms of havens, functions describing an evasion strategy for a certain pursuit–evasion game defined on a graph. A graph G has treewidth k if and only if it has a haven of order k + 1 but of no higher order, where a haven of order k + 1 is a function β that maps each set X of at most k vertices in G into one of the connected components of G X and that obeys the monotonicity property that β(Y) ⊆ β(X) whenever X ⊆ Y.

A similar characterization can also be made using brambles, families of connected subgraphs that all touch each other (meaning either that they share a vertex or are connected by an edge).^[3] The order of a bramble is the smallest hitting set for the family of subgraphs, and the treewidth of a graph is one less than the maximum order of a bramble.

Examples[edit]

Every complete graph K_n has treewidth n – 1. This is most easily seen using the definition of treewidth in terms of chordal graphs: the complete graph is already chordal, and adding more edges cannot reduce the size of its largest clique.

A connected graph with at least two vertices has treewidth 1 if and only if it is a tree. A tree has treewidth one by the same reasoning as for complete graphs (namely, it is chordal, and has maximum clique size two). Conversely, if a graph has a cycle, then every chordal completion of the graph includes at least one triangle consisting of three consecutive vertices of the cycle, from which it follows that its treewidth is at least two.

Bounded treewidth[edit]

Graph families with bounded treewidth[edit]

For any fixed constant k, the graphs of treewidth at most k are called the partial k-trees. Other families of graphs with bounded treewidth include the cactus graphs, pseudoforests, series–parallel graphs, outerplanar graphs, Halin graphs, and Apollonian networks.^[4] The control-flow graphs arising in the compilation of structured programs also have bounded treewidth, which allows certain tasks such as register allocation to be performed efficiently on them.^[5]

The planar graphs do not have bounded treewidth, because the n × n grid graph is a planar graph with treewidth exactly n. Therefore, if F is a minor-closed graph family with bounded treewidth, it cannot include all planar graphs. Conversely, if some planar graph cannot occur as a minor for graphs in family F, then there is a constant k such that all graphs in F have treewidth at most k. That is, the following three conditions are equivalent to each other:^[6]

1. F is a minor-closed family of bounded-treewidth graphs;
2. One of the finitely many forbidden minors characterizing F is planar;
3. F is a minor-closed graph family that does not include all planar graphs.

Forbidden minors[edit]

For every finite value of k, the graphs of treewidth at most k may be characterized by a finite set of forbidden minors. (That is, any graph of treewidth > k includes one of the graphs in the set as a minor.) Each of these sets of forbidden minors includes at least one planar graph.

• For k = 1, the unique forbidden minor is a 3-vertex cycle graph.^[7]
• For k = 2, the unique forbidden minor is the 4-vertex complete graph K₄.^[7]
• For k = 3, there are four forbidden minors: K₅, the graph of the octahedron, the pentagonal prism graph, and the Wagner graph. Of these, the two polyhedral graphs are planar.^[8]

For larger values of k, the number of forbidden minors grows at least as quickly as the exponential of the square root of k.^[9] However, known upper bounds on the size and number of forbidden minors are much higher than this lower bound.^[10]

Algorithms[edit]

Computing the treewidth[edit]

It is NP-complete to determine whether a given graph G has treewidth at most a given variable k.^[11]
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.^[12] The time dependence of this algorithm on k is exponential.

Due to the roles the treewidth plays in an enormous number of fields, different practical and theoretical algorithms computing the treewidth of a graph were developed. Depending on the application on hand, one can prefer better approximation ratio, or better dependence in the running time from the size of the input or the treewidth.
The table below provides an overview of some of the treewidth algorithms. Here k is the treewidth and n is the number of vertices of an input graph G.
Each of the algorithms outputs in time f(k) ⋅ g(n) a decomposition of width given in the Approximation column. For example, the algorithm of Bodlaender (1996) in time 2^O(k3)⋅n either constructs a tree decomposition of the input graph G of width at most k or reports that the treewidth of G is more than k. Similarly, the algorithm of Bodlaender et al. (2016) in time 2^O(k)⋅n either constructs a tree decomposition of the input graph G of width at most 5k + 4 or reports that the treewidth of G is more than k. Korhonen (2021) improved this to 2k + 1 in the same running time.

Approximation	f(k)	g(n)	reference
exact	O(1)	O(nk+2)	Arnborg, Corneil & Proskurowski (1987)
4k + 3	O(33k)	O(n2)	Robertson & Seymour (1995)
8k + 7	2O(k log k)	n log2 n	Lagergren (1996)
5k + 4 (or 7k + 6)	2O(k log k)	n log n	Reed (1996)
exact	2O(k3)	O(n)	Bodlaender (1996)
	O(1)	nO(1)	Feige, Hajiaghayi & Lee (2008)
4.5k + 4	23k	n2	Amir (2010)
11/3k + 4	23.6982k	n3 log4n	Amir (2010)
exact	O(1)	O(1.7347n)	Fomin, Todinca & Villanger (2015)
3k + 2	2O(k)	O(n log n)	Bodlaender et al. (2016)
5k + 4	2O(k)	O(n)	Bodlaender et al. (2016)
k2	O(k7)	O(n log n)	Fomin et al. (2018)
5k + 4	28.765k	O(n log n)	Belbasi & Fürer (2021a)
2k + 1	2O(k)	O(n)	Korhonen (2021)
5k + 4	26.755k	O(n log n)	Belbasi & Fürer (2021b)
exact	2O(k2)	n4	Korhonen & Lokshtanov (2022)
(1+)k	kO(k/)	n4	Korhonen & Lokshtanov (2022)

It is not known whether determining the treewidth of planar graphs is NP-complete, or whether their treewidth can be computed in polynomial time.^[13]

In practice, an algorithm of Shoikhet & Geiger (1997) can determine the treewidth of graphs with up to 100 vertices and treewidth up to 11, finding a chordal completion of these graphs with the optimal treewidth.

For larger graphs, one can use search-based techniques such as branch and bound search (BnB) and best-first search to compute the treewidth. These algorithms are anytime in that when stopped early, they will output an upper bound on the treewidth.

The first BnB algorithm for computing treewidth, called the QuickBB algorithm^[14] was proposed by Gogate and Dechter.^[15] Since the quality of any BnB algorithm is highly dependent on the quality of the lower bound used, Gogate and Dechter^[15] also proposed a novel algorithm for computing a lower-bound on treewidth called minor-min-width.^[15] At a high level, the minor-min-width algorithm combines the facts that the treewidth of a graph is never larger than its minimum degree or its minor to yield a lower bound on treewidth. The minor-min-width algorithm repeatedly constructs a graph minor by contracting an edge between a minimum degree vertex and one of its neighbors, until just one vertex remains. The maximum of the minimum degree over these constructed minors is guaranteed to be a lower bound on the treewidth of the graph.

Dow and Korf^[16] improved the QuickBB algorithm using best-first search. On certain graphs, this best-first search algorithm is an order of magnitude faster than QuickBB.

Solving other problems on graphs of small treewidth[edit]

At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non serial dynamic programming as long as the graph had a bounded dimension,^[17] a parameter shown to be equivalent to treewidth by Bodlaender (1998). Later, several authors independently observed at the end of the 1980s^[18] 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, the problem of coloring a graph of treewidth k may be solved by using a dynamic programming algorithm on a tree decomposition of the graph. For each set X_i of the tree decomposition, and each partition of the vertices of X_i into color classes, the algorithm determines whether that coloring is valid and can be extended to all descendant nodes in the tree decomposition, by combining information of a similar type computed and stored at those nodes. The resulting algorithm finds an optimal coloring of an n-vertex graph in time O(k^k+O(1)n), a time bound that makes this problem fixed-parameter tractable.

Courcelle’s theorem[edit]

For a large class of problems, there is a linear time algorithm to solve a problem from the class if a tree-decomposition with constant bounded treewidth is provided. Specifically, Courcelle’s theorem^[19] states that if a graph problem can be expressed in the logic of graphs using monadic second order logic, then it can be solved in linear time on graphs with bounded treewidth. Monadic second order logic is a language to describe graph properties that uses the following constructions:

• Logic operations, such as
• Membership tests, such as e ∈ E, v ∈ V
• Quantifications over vertices, edges, sets of vertices, and/or sets of edges, such as ∀v ∈ V, ∃e ∈ E, ∃I ⊆ V, ∀F ⊆ E
• Adjacency tests (u is an endpoint of e), and some extensions that allow for things such as optimization.

Consider for example the 3-coloring problem for graphs. For a graph G = (V, E), this problem asks if it is possible to assign each vertex v ∈ Vone of the 3 colors such that no two adjacent vertices are assigned the same color.
This problem can be expressed in monadic second order logic as follows:

,

where W₁, W₂, W₃ represent the subsets of vertices having each of the 3 colors.
Therefore, by Courcelle’s results, the 3-coloring problem can be solved in linear time for a graph given a tree-decomposition of bounded constant treewidth.

[edit]

Pathwidth[edit]

The pathwidth of a graph has a very similar definition to treewidth via tree decompositions, but is restricted to tree decompositions in which the underlying tree of the decomposition is a path graph. Alternatively, the pathwidth may be defined from interval graphs analogously to the definition of treewidth from chordal graphs. As a consequence, the pathwidth of a graph is always at least as large as its treewidth, but it can only be larger by a logarithmic factor.^[4] Another parameter, the graph bandwidth, has an analogous definition from proper interval graphs, and is at least as large as the pathwidth. Other related parameters include the tree-depth, a number that is bounded for a minor-closed graph family if and only if the family excludes a path, and the degeneracy, a measure of the sparsity of a graph that is at most equal to its treewidth.

Grid minor size[edit]

Because the treewidth of an n × n grid graph is n, the treewidth of a graph G is always greater than or equal to the size of the largest square grid minor of G. In the other direction, the grid minor theorem by Robertson and Seymour shows that there exists an unbounded function f such that the largest square grid minor has size at least f(r) where r is the treewidth.^[20] The best bounds known on f are that f must be at least Ω(r^d) for some fixed constant d > 0, and at most^[21]

For the Ω notation in the lower bound, see big O notation. Tighter bounds are known for restricted graph families, leading to efficient algorithms for many graph optimization problems on those families through the theory of bidimensionality.^[22]
Halin’s grid theorem provides an analogue of the relation between treewidth and grid minor size for infinite graphs.^[23]

Diameter and local treewidth[edit]

A family F of graphs closed under taking subgraphs is said to have bounded local treewidth, or the diameter-treewidth property, if the treewidth of the graphs in the family is upper bounded by a function of their diameter. If the class is also assumed to be closed under taking minors, then F has bounded local treewidth if and only if one of the forbidden minors for F is an apex graph.^[24] The original proofs of this result showed that treewidth in an apex-minor-free graph family grows at most doubly exponentially as a function of diameter;^[25] later this was reduced to singly exponential^[22] and finally to a linear bound.^[26]
Bounded local treewidth is closely related to the algorithmic theory of bidimensionality,^[27] and every graph property definable in first order logic can be decided for an apex-minor-free graph family in an amount of time that is only slightly superlinear.^[28]

It is also possible for a class of graphs that is not closed under minors to have bounded local treewidth. In particular this is trivially true for a class of bounded degree graphs, as bounded diameter subgraphs have bounded size. Another example is given by 1-planar graphs, graphs that can be drawn in the plane with one crossing per edge, and more generally for the graphs that can be drawn on a surface of bounded genus with a bounded number of crossings per edge. As with minor-closed graph families of bounded local treewidth, this property has pointed the way to efficient approximation algorithms for these graphs.^[29]

Hadwiger number and S-functions[edit]

Halin (1976) defines a class of graph parameters that he calls S-functions, which include the treewidth. These functions from graphs to integers are required to be zero on graphs with no edges, to be minor-monotone (a function f is referred to as «minor-monotone» if, whenever H is a minor of G, one has f(H) ≤ f(G)), to increase by one when a new vertex is added that is adjacent to all previous vertices, and to take the larger value from the two subgraphs on either side of a clique separator. The set of all such functions forms a complete lattice under the operations of elementwise minimization and maximization. The top element in this lattice is the treewidth, and the bottom element is the Hadwiger number, the size of the largest complete minor in the given graph.

Notes[edit]

References[edit]

Да, он всегда будет выдавать константное значение, а именно 0. Нужно заменить строчку return Math.max(left, right); на return Math.max(left, right) + 1;. Исправленный вариант:

static class Node {
    Node left;
    Node right;

    static int height(Node node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        int right = height(node.right);
        return Math.max(left, right) + 1;
    }
}

Хочу заметить, что этот метод вычисляет не ширину дерева, а высоту, то есть расстояние от корня до самого глубокого листа. Если вы хотите вычислять не высоту, а ширину дерева, то сначала стоит определить, что такое ширина дерева. Например, можно определить её как максимальная ширина уровня дерева, где ширина уровня дерева есть число вершин, находящихся на некотором уровне, то есть на одинаковом расстоянии от корня. Тогда алгоритм вычисления ширины дерева выглядит следующим образом:

1. Найдём глубину дерева уже написанным методом. Обозначим её за h.
2. Всего уровней в дереве ровно h + 1. Заведём массив на h + 1 элементов, в i-ой его ячейке будет записано число вершин на i-ом уровне. Изначально массив заполнен нулями.
3. Обойдём дерево любым алгоритмом, в процессе увеличивая соответствующие ячейки массива.
4. По нашему определению ширина дерева равна максимуму элементов в этом массиве.

Собственно, код:

static class Node {
    Node left;
    Node right;

    static int height(Node node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        int right = height(node.right);
        return Math.max(left, right) + 1;
    }

    static void dfs(Node node, int nodeHeight, int[] numberVertexesOnLevels) {
        ++numberVertexesOnLevels[nodeHeight];
        dfs(node.left, nodeHeight + 1, numberVertexesOnLevels);
        dfs(node.right, nodeHeight + 1, numberVertexesOnLevels);
    }

    static int width(Node node) {
        int height = height(node);
        int[] numberVertexesOnLevels = new int[height];
        dfs(node, 0, numberVertexesOnLevels);
        return Arrays.stream(numberVertexesOnLevels).max().getAsInt();
    }
}

Введение

В этом посте я сделаю демонстрацию кода о том, как найти ширину двоичного дерева.

Шаг 1: Начните с класса узла дерева

Шаг 2: Напишите шаблонный код для создания дерева, на котором мы будем играть.

Шаг 3: Сначала мы найдем высоту бинарного дерева

Шаг 4: Затем мы рассчитаем количество элементов на каждом уровне двоичного дерева.

Шаг 5: Затем мы найдем максимальный уровень, который завершен, и количество элементов на максимальном полном уровне даст нам ширину

Шаг 6: Проверьте вывод кода

Вывод

Если вам понравился этот пост, подпишитесь на меня в инсте: https://www.instagram.com/global.software.developers/?hl=en

Если вам понравился этот пост, подпишитесь на меня в инсте: https://www.instagram.com/global.software.developers/?hl=en

ширина дерева

В теории графов и теоретической информатике древовидная ширина графа представляет собой число , которое интуитивно измеряет, насколько он близок к дереву ^{[ 1 ]} . Его можно определить несколькими способами ^{[Какими?]} , в частности, с помощью декомпозиции дерева .

Часто простая алгоритмическая задача на деревьях на самом деле проста на древовидных графах. Таким образом, этот параметр часто используется в графовых алгоритмах, особенно для схем полиномиальной аппроксимации и параметризованной сложности . Во многих приложениях графы имеют небольшую ширину дерева ^{[ref. необходимо]} , такие как социальные сети.

Определение

С разложением дерева

Определение декомпозиции дерева

Неформально, учитывая неориентированный граф , древовидная декомпозиция представляет собой дерево , узлы которого аннотируются подмножествами вершин , которые удовлетворяют следующим условиям:

• каждая вершина появляется в метке узла  ;
• для любого ребра существует узел метки которого содержит и  ;
• для любой вершины , узлы дерева, которые содержат , образуют связное поддерево .

Формально для данного неориентированного графа древовидная декомпозиция представляет собой пару , где — дерево, и представляет собой функцию , ассоциированную с каждым узлом подмножества , которое удовлетворяет следующим условиям:

• Для любой вершины существует такой узел дерева , что . Это условие сводится к тому, что союз равен .
• Для любого ребра существует такой узел , что .
• Для любой вершины узлы образуют связанное поддерево . Это условие сводится к наложению того, что для всех узлов и , которые содержат одну и ту же вершину (то есть и ) , все узлы единственной простой цепи между и также удовлетворяют .

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

Настройка ширины дерева

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

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

Через триангуляции

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

Примеры

Деревья имеют ширину дерева 1. Клика размера n имеет ширину дерева n-1 . Квадратная сетка размера n имеет ширину дерева , равную n ^{[ 2 ]} .

Алгоритмические аспекты

Расчет ширины дерева

Вычисление ширины дерева является NP-трудным ^{[ 3 ]} . Однако, если фиксировано, существует линейный алгоритм для определения того, равна ли ширина дерева графа . Однако зависимость от времени выполнения алгоритма носит экспоненциальный характер. Для некоторых конкретных классов графов вычисление ширины дерева выполняется за полиномиальное время (деревья, триангулированные графы и т. д.).

Использование в алгоритмах

Многие NP-трудные графовые задачи в общем случае могут быть решены за полиномиальное время, если ограничиться графами ограниченной древесной ширины. Следовательно, это хороший параметр для параметризованной сложности . Если проблема выразима в монадической логике второго порядка , теорема Курселя ^{[ 4 ]} утверждает, что тогда ее можно решить за линейное время (но константа представляет собой башню экспонент, в которой алгоритм вообще неприменим).

Например, максимально устойчивая задача для плоских графов может быть решена за полиномиальное время при ограниченной ширине дерева (мы тогда примем эту ширину за константу) ^{[ 5 ]} , что позволяет получить схему аппроксимации за полиномиальное время при ширине не ограничен.

Связи с триангулированными графами

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

Связанные настройки графика

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

Определен вариант для ориентированных графов, он равен нулю на ориентированных ациклических графах ^{[ 6 ]} .

Библиография

Работает

• (в) Дэвид П. Уильямсон и Дэвид Б. Шмойс , Разработка алгоритмов аппроксимации , Издательство Кембриджского университета ,2010, 500  р. ( онлайн презентация , читать онлайн )
• (en) Ганс Л. Бодлендер, «  Путеводитель по дереву  » , Технический отчет RUU-CS , vol.  92.‎1993 г. ( читать онлайн )

Предметы

• С. Арнборг , Д. Корнейл и А. Проскуровски , «  Сложность поиска вложений в k — дерево  », SIAM Journal on Matrix Analysis and Applications , vol.  8, № ²  ,1987 г., с.  277–284 ( DOI  10.1137/0608024 )

Примечания и ссылки

Связанная статья

• Ширина клика

В теории графов , то древесная ширина неориентированного графа представляет собой целое число, определяющее, неформально, как далека графы от того , чтобы дерево . Наименьшая ширина дерева — 1; графы с шириной дерева 1 — это в точности деревья и леса . Графики с шириной дерева не более 2 являются последовательно -параллельными графами . Максимальные графы с шириной дерева ровно k называются k-деревьями , а графы с шириной дерева не выше k называются частичными k -деревьями . Многие другие хорошо изученные семейства графов также имеют ограниченную древовидную ширину.

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

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

Концепция ширины дерева была первоначально введена Умберто Бертеле и Франческо Бриоски ( 1972 ) под названием « измерение» . Позже он был переоткрыт Рудольфом Халином  ( 1976 ) на основе свойств, которые он разделяет с другим параметром графа, числом Хадвигера . Позже он был снова открыт Нилом Робертсоном и Полом Сеймуром  ( 1984 ) и с тех пор изучается многими другими авторами.

Определение

Разложение дерева графа G = ( V , E ) является деревом, Т , с узлами Х ₁ , …, Х _п , где каждый Х _я есть подмножество V , удовлетворяющая следующие свойства (термин узел является используется для обозначения вершины T, чтобы избежать путаницы с вершинами G ):

1. Объединение всех множеств X _я равен V . То есть каждая вершина графа содержится как минимум в одном узле дерева.
2. Если X _i и X _j оба содержат вершину v , то все узлы X _k из T на (уникальном) пути между X _i и X _{j также} содержат v . Эквивалентно, узлы дерева , содержащие вершину V образуют связное поддерево T .
3. Для каждого ребра ( v , w ) в графе существует подмножество X _i, которое содержит как v, так и w . То есть вершины смежны в графе только тогда, когда соответствующие поддеревья имеют общий узел.

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

Эквивалентно, ширина дерева G на единицу меньше размера самой большой клики в хордальном графе, содержащем G с наименьшим номером клики . Хордовый граф с таким размером клики может быть получен добавлением к G ребра между каждыми двумя вершинами, которые обе принадлежат хотя бы одному из множеств X _i .

Treewidth также можно охарактеризовать в терминах убежищ , функций, описывающих стратегию уклонения для определенной игры преследования-уклонения, определенной на графе. Граф G имеет древовидную ширину k тогда и только тогда, когда он имеет убежище порядка k + 1, но не более высокого порядка, где убежище порядка k + 1 — это функция β, которая отображает каждое множество X не более чем из k вершин в G в одна из компонент связности G X и, подчиняющийся монотонности свойством , что & beta ; ( Y ) ⊆ & beta ; ( Х ) всякий раз , когда X ⊆ Y .

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

Примеры

Каждый полный граф K _n имеет ширину дерева n  — 1. Это легче всего увидеть, используя определение ширины дерева в терминах хордовых графов: полный граф уже является хордовым, и добавление дополнительных ребер не может уменьшить размер его наибольшей клики.

Связный граф с минимум двумя вершинами имеет ширину дерева 1 тогда и только тогда, когда он является деревом. Дерево имеет древовидную ширину, равную единице, по тем же соображениям, что и для полных графов (а именно, оно хордовое и имеет максимальный размер клики два). И наоборот, если у графа есть цикл, то каждое хордовое пополнение графа включает по крайней мере один треугольник, состоящий из трех последовательных вершин цикла, из чего следует, что его ширина по дереву не меньше двух.

Ограниченная ширина дерева

Семейства графов с ограниченной шириной дерева

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

В плоских графах не имеют ограниченную древесную ширину, поскольку п × п решетчатый граф является планарным графом с древесной шириной точно п . Следовательно, если F — семейство минорно-замкнутых графов с ограниченной шириной дерева, оно не может включать все плоские графы. И наоборот, если некоторый планарный граф не может быть второстепенным для графов семейства F , тогда существует константа k такая, что все графы в F имеют ширину дерева не более k . То есть следующие три условия эквивалентны друг другу:

1. F — минорно-замкнутое семейство графов с ограниченной шириной дерева;
2. Один из конечного числа запрещенных миноров, характеризующих F, является плоским;
3. F — семейство минорно-замкнутых графов, которое не включает все плоские графы.

Запрещенные несовершеннолетние

Для любого конечного значения k графы с шириной не более k могут быть охарактеризованы конечным набором запрещенных миноров . (То есть любой граф с шириной дерева> k включает в себя один из графов в наборе в качестве второстепенного.) Каждый из этих наборов запрещенных миноров включает по крайней мере один планарный граф.

• При k = 1 единственным запрещенным минором является трехвершинный граф циклов .
• При k = 2 единственным запрещенным минором является 4-вершинный полный граф K ₄ .
• При k = 3 существует четыре запрещенных минора: K ₅ , граф октаэдра , граф пятиугольной призмы и граф Вагнера . Из них два многогранных графа плоские.

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

Алгоритмы

Вычисление ширины дерева

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

Из-за роли, которую ширина дерева играет в огромном количестве полей, были разработаны различные практические и теоретические алгоритмы вычисления ширины дерева графа. В зависимости от используемого приложения можно предпочесть лучший коэффициент аппроксимации или лучшую зависимость времени выполнения от размера ввода или ширины дерева. В таблице ниже представлен обзор некоторых алгоритмов ширины дерева. Вот ширина дерева и количество вершин входного графа . Каждый из алгоритмов выводит по времени разложение ширины, указанной в столбце Приближение. Например, алгоритм Bodlaender (1996) во времени либо строит древовидное разложение входного графа шириной не больше, либо сообщает, что ширина
дерева больше чем
. Аналогичным образом алгоритм Bodlaender et al. (2016) со временем либо строит древовидную декомпозицию входного графа шириной не более, либо сообщает, что ширина
дерева больше, чем
. Корхонен (2021) улучшил это до того же времени.

Приближение	f (k)	г (п)	ссылка
точный			Арнборг, Корнейл и Проскуровски (1987)
			Робертсон и Сеймур (1995)
			Лагергрен (1996)
			Рид (1992)
точный			Бодлендер (1996)
			Файги, Хаджиагайи и Ли (2008)
			Амир (2010)
			Амир (2010)
точный			Фомин, Тодинка и Вилланджер (2015)
			Bodlaender et al. (2016)
			Bodlaender et al. (2016)
			Фомин и др. (2018)
			Бельбаси и Фюрер (2020)
			Корхонен (2021 г.)

Неизвестно, является ли определение ширины дерева планарных графов NP-полным, или их ширина дерева может быть вычислена за полиномиальное время.

На практике алгоритм Шойхета и Гейгера (1997) может определять ширину дерева графов до 100 вершин и ширину дерева до 11, находя хордовое завершение этих графов с оптимальной шириной дерева.

Решение других задач на графах малой ширины дерева

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

Например, проблема раскраски графа с шириной дерева k может быть решена с помощью алгоритма динамического программирования на древовидной декомпозиции графа. Для каждого набора X _i разложения дерева и каждого разбиения вершин X _i на классы цветов алгоритм определяет, является ли эта раскраска допустимой и может ли быть расширена на все узлы-потомки в разложении дерева путем объединения информации аналогичных type вычисляется и хранится в этих узлах. Результирующий алгоритм находит оптимальную раскраску n- вершинного графа за время O ( k ^{k  +  O (1)} n ), ограничение по времени, которое делает эту задачу с фиксированным параметром решаемой .

Теорема Курселя

Для большого класса задач существует алгоритм линейного времени для решения задачи из класса, если предусмотрено дерево-разложение с постоянной ограниченной шириной дерева . В частности, теорема Курселя утверждает, что если проблема графа может быть выражена в логике графов с использованием монадической логики второго порядка , то она может быть решена за линейное время на графах с ограниченной шириной дерева. Monadic логика второго порядка является языком для описания свойств графов , которые используются следующими конструкции: логические операции ( ), членство тесты (например, ), количественные над вершинами, ребра, множество вершин, множество ребер (например, , , , ), тесты на смежность ( u — конечная точка e ) и некоторые расширения, которые позволяют выполнять такие операции, как оптимизация.

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

,

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

Ширина пути

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

Младший размер сетки

Поскольку древесная ширина из п  ×  п сеточного графа является п , то древесная ширина графа G всегда больше или равен размеру самого большого квадрата сетки минор из G . В другом направлении, то теорема сетки незначительные по Robertson и Seymour показывает , что существует функция ф такая , что древесная ширина составляет не более е ( г ) , где г является размер самого большого квадрата сетки минор. Наилучшие известные оценки для f состоят в том, что f должно быть не меньше Ω ( r ^d ) для некоторой фиксированной константы d > 0 и не больше O ( √ r / log r ). Для семейств ограниченных графов известны более жесткие границы, что приводит к эффективным алгоритмам для многих задач оптимизации графов для этих семейств с помощью теории двумерности .
Теорема Халина о сетке обеспечивает аналог отношения между шириной дерева и второстепенным размером сетки для бесконечных графов.

Диаметр и местная ширина дерева

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

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

Число Хадвигера и S- функции

Халин (1976) определяет класс параметров графа, которые он называет S- функциями, которые включают ширину дерева. Эти функции от графов к целым числам должны быть равны нулю на графах без ребер , чтобы быть минорно-монотонными (функция f называется «минорно-монотонной», если, когда H является минором G , одна имеет f (H ) ≤ f (G)), чтобы увеличиваться на единицу, когда добавляется новая вершина, смежная со всеми предыдущими вершинами, и брать большее значение из двух подграфов по обе стороны от разделителя клик . Набор всех таких функций образует полную решетку при операциях поэлементной минимизации и максимизации. Верхний элемент в этой решетке — это ширина дерева, а нижний элемент — это число Хадвигера , размер наибольшего полного минора в данном графе.

Примечания

использованная литература