Cluster Trees are also called Tree Decompositions, Junction Trees, Clique Trees, or Join Trees
- is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph
- is a cluster graph with no cycles
- they play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition
Tree Decompositiongiven a graph 𝐆=(𝐕𝑔,𝐄𝑔) where:
- 𝐕𝑔= {𝑣1, …, 𝑣𝑟} are vertices of 𝐆
- 𝐄𝑔= {…} are edges of 𝐆
a tree decomposition of 𝐆 is a tree 𝐓=(𝐕𝑡𝑑,𝐄𝑡𝑑) where:
- 𝐕𝑡𝑑 = {𝑉𝑡𝑑1, …, 𝑉𝑡𝑑𝑛} are nodes of 𝐓, where each node 𝑉𝑡𝑑𝑖is a subset of 𝐕𝑔
- 𝐄𝑡𝑑= {𝐸𝑡𝑑1, …, 𝐸𝑡𝑑𝑚} are edges of 𝐓
and 𝐓=(𝐕𝑡𝑑,𝐄𝑡𝑑) must satisfying the following properties:
- the union of all 𝑉𝑡𝑑𝑖‘s = 𝐕𝑔
- if 𝑉𝑡𝑑𝑖and 𝑉𝑡𝑑𝑗both contain a vertex 𝑣, then all nodes in the path between 𝑉𝑡𝑑𝑖and 𝑉𝑡𝑑𝑗also contains 𝑣. Equivalently, the tree nodes containing vertex 𝑣 form a connected subtree of 𝐓
- for every edge (𝑢,𝑣) in graph 𝐆, there exist a node 𝑉𝑡𝑑𝑖 in 𝐓 that contains both 𝑢 and 𝑣
Tree-Width
- treewidth of a tree decomposition 𝐓 is the size of its largest node 𝑉𝑡𝑑𝑖 minus 1
- treewidth of a graph 𝐆 is:
- the minimum treewidth among all possible tree decompositions of 𝐆
- 1 less than the size of the largest clique in the chordal graph containing 𝐆 with the smallest clique number
- Tree Width vs Induced Width
Example Tree Decomposition & Tree-Width
|
|
Tree DecompositionA graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. does the tree decomposition have the 3 properties? YES!
Tree-Width
|
