Treewidth of a graph

Treewidth of a graph --- древесная ширина дерева.

The minimum value [math]\displaystyle{ k }[/math] for which a graph is a subgraph of a [math]\displaystyle{ k }[/math]-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 [math]\displaystyle{ G = (V,E) }[/math] is a pair [math]\displaystyle{ D = (S,T) }[/math], where [math]\displaystyle{ S = \{X_{i}| i \in I\} }[/math] is a collection of subsets of vertices of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ T = (I,F) }[/math] a tree, with one node for each subset of [math]\displaystyle{ S }[/math], such that the following three conditions are satisfied:

(1) [math]\displaystyle{ \cup_{i \in I}X_{i} = V }[/math],

(2) for all edges [math]\displaystyle{ (v,w) \in E }[/math], there is a subset [math]\displaystyle{ X_{i} \in S }[/math] such that both [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] are contained in [math]\displaystyle{ X_{i} }[/math],

(3) for each vertex [math]\displaystyle{ x }[/math], the set of nodes [math]\displaystyle{ \{i|x \in X_{i}\} }[/math] forms a subtree of [math]\displaystyle{ T }[/math].

The width of a tree-decomposition [math]\displaystyle{ (\{X_{i}| i \in I\}, T = (I,F)) }[/math] is [math]\displaystyle{ \max_{i \in I}(|X_{i}| - 1) }[/math]. The treewidth of a graph [math]\displaystyle{ G }[/math] equals the minimum width over all tree-decompositions of [math]\displaystyle{ G }[/math].