Editing Tree decomposition (section)

==Definition==
Intuitively, a tree decomposition represents the vertices of a given graph {{mvar|G}} as subtrees of a tree, in such a way that vertices in {{mvar|G}} are adjacent only when the corresponding subtrees intersect. Thus, {{mvar|G}} forms a [[Glossary of graph theory#Subgraphs|subgraph]] of the [[intersection graph]] of the subtrees. The full intersection graph is a [[chordal graph]].

Each subtree associates a graph vertex with a set of tree nodes. To define this formally, we represent each tree node as the set of vertices associated with it.
Thus, given a graph {{math|1=''G'' = (''V'', ''E'')}}, a tree decomposition is a pair {{math|(''X'', ''T'')}}, where {{math|1=''X'' = {''X''{{sub|1}}, …, ''X{{sub|n}}''} }} is a family of subsets (sometimes called ''bags'') of {{mvar|V}}, and {{mvar|T}} is a tree whose nodes are the subsets {{mvar|X{{sub|i}}}}, satisfying the following properties:<ref>{{harvtxt|Diestel|2005}} section 12.3</ref>

# The union of all sets {{mvar|X{{sub|i}}}} equals {{mvar|V}}. That is, each graph vertex is associated with at least one tree node.
# For every edge {{math|(''v'', ''w'')}} in the graph, there is a subset {{mvar|X{{sub|i}}}} that contains both {{mvar|v}} and {{mvar|w}}. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.
# If {{mvar|X{{sub|i}}}} and {{mvar|X{{sub|j}}}} both contain a vertex {{mvar|v}}, then all nodes {{mvar|X{{sub|k}}}} of the tree in the (unique) path between {{mvar|X{{sub|i}}}} and {{mvar|X{{sub|j}}}} contain {{mvar|v}} as well. That is, the nodes associated with vertex {{mvar|v}} form a connected subset of {{mvar|T}}. This is also known as coherence, or the ''running intersection property''. It can be stated equivalently that if {{mvar|X{{sub|i}}}}, {{mvar|X{{sub|j}}}} and {{mvar|X{{sub|k}}}} are nodes, and {{mvar|X{{sub|k}}}} is on the path from {{mvar|X{{sub|i}}}} to {{mvar|X{{sub|j}}}}, then <math>X_i \cap X_j \subseteq X_k</math>.

The tree decomposition of a graph is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node.

A tree decomposition in which the underlying tree is a [[path graph]] is called a path decomposition, and the width parameter derived from these special types of tree decompositions is known as [[pathwidth]].

A tree decomposition {{math|1=(''X'', ''T'' = (''I'', ''F''))}} of treewidth {{mvar|k}} is ''smooth'', if for all <math>i \in I : |X_i| = k + 1</math>, and for all <math>(i, j) \in F : |X_i \cap X_j| = k</math>.<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref>