Tree decomposition
In
graph theory a
tree decomposition D of a
graph G = (V, E) is a pair (
X = {
Xi :
i in
I},
T = (
I,
F)) such that {
Xi :
i in
I} if a family of subsets of
V, one for every node of
T, and
T is a tree such that the following properties hold:
P1: the union of all {Xi, i in I, equals to V;
P2: for every edge (v, w) in E, the is an i in I such that v and w are in Xi;
P3: for every i, j and k in I, if j is in a path between i and k in T, then the intersection of Xi and Xk is contained in Xj.