|
|
|
|
|
Tree DecompositionIn 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} is 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 V; P2: for every edge (v, w) in E, there 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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|