Treewidth of a graph

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

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

(1) $\cup_{i \in I}X_{i} = V$,

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

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

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