Графтардың ағашқа жақындығын көрсететін сан

Number denoting a graph's closeness to a tree

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 under the name of dimension. It was later rediscovered by , based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by and has since been studied by many other authors.

Every complete graph 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.

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 1=k = 1, the unique forbidden minor is a 3 vertex cycle graph. For 1=k = 2, the unique forbidden minor is the 4 vertex complete graph For larger values of k, the number of forbidden minors grows at least as quickly as the exponential of the square root of k. However, known upper bounds on the size and number of forbidden minors are much higher than this lower bound.

It is NP complete to determine whether a given graph G has treewidth at most a given variable k.
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. 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 in time 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 in time 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. improved this to 2k + 1 in the same running time. Approximation f(k) g(n) reference exact O(1) 4k + 3 8k + 7 5k + 4 (or 7k + 6) n log n exact O(n) O(1) 4.5k + 4 exact O(1) 3k + 2 O(n log n) 5k + 4 O(n) O(n log n) 5k + 4 O(n log n) 2k + 1O(n) 5k + 4 O(n log n) exact (1+)k

It is not known whether determining the treewidth of planar graphs is NP complete, or whether their treewidth can be computed in polynomial time. In practice, an algorithm of 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 was proposed by Gogate and Dechter. Since the quality of any BnB algorithm is highly dependent on the quality of the lower bound used, Gogate and Dechter improved the QuickBB algorithm using best first search. On certain graphs, this best first search algorithm is an order of magnitude faster than QuickBB.

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, a parameter shown to be equivalent to treewidth by Later, several authors independently observed at the end of the 1980s 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 of the tree decomposition, and each partition of the vertices of 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.

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. The best bounds known on f are that f must be at least Ω(r^(d)) for some fixed constant d > 0, and at most

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. Halin's grid theorem provides an analogue of the relation between treewidth and grid minor size for infinite graphs.

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. 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; later this was reduced to singly exponential and finally to a linear bound. Bounded local treewidth is closely related to the algorithmic theory of bidimensionality, 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. 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.

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.