Treewidth of a graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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.