Treewidth

The tree-width is a term from graph theory. It tells how a graph is " tree - like". Since many algorithms on trees (or tree-decompositions ) run efficiently, which do not in general graphs, it is interesting to know the tree-width. Tree and path length are largely analogous to each other.

Formal definition

A tree decomposition of a pair, with a tree and a family of subsets of the node set of the graph is, so that:

• .
• For all edges there is a with.
• For all true: when is on the path from to in, then.

The width of the tree decomposition of is defined as.

The tree-width of a graph G is defined as the smallest width of all tree decompositions of G.

Explanation

Understandable words, we distribute the nodes of G on bags ( English: buckets or bags) that are arranged in a tree structure.

The following rules apply:

• Each node is in at least one case,
• The two end nodes of each edge are together in at least one pocket and
• For each node constituting the bags which contain a sub-tree.

The width of a tree decomposition is the maximum number of nodes in a single bag - 1 The subtraction of 1 causes the tree-width of trees is 1. Without this subtraction trees have tree-width 2

Tree-width special graph classes

Determining the treewidth of a given graph is an NP -complete problem under general conditions. However, the tree lengths of some graph classes can be estimated according to the above:

• Each tree has a tree-width of at most 1
• Series parallel graphs have tree-width at most 2
• Halingraphen have a tree-width at most 3