Main Page | See live article | Alphabetical index 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. This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.