Treewidth of a graph
Treewidth of a graph --- древесная ширина дерева.
The minimum value for which a graph is a subgraph of a -tree. One can also define the treewidth of a graph by a concept called the tree-decomposition of a graph.
A tree-decomposition of a graph is a pair , where is a collection of subsets of vertices of and a tree, with one node for each subset of , such that the following three conditions are satisfied:
(2) for all edges , there is a subset such that both and are contained in ,
(3) for each vertex , the set of nodes forms a subtree of .
The width of a tree-decomposition is . The treewidth of a graph equals the minimum width over all tree-decompositions of .