A tree decomposition is a mapping of a graph into a related tree with desirable properties that allow it to be used to efficiently compute certain properties (e.g., independence polynomial) of the original graph. The tree decomposition of a graph is not unique and need not be isomorphic to the original graph. Tree decompositions are also known as clique trees, join trees, and junction trees.
A measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition is known as the treewidth.
See also
Explore with Wolfram|Alpha
References
Bulatov, Y. "Tree Decomposition Package."
http://mathematica-bits.blogspot.com/2011/01/tree-decomposition-package.html.
Jan. 21, 2011.Robertson, N. and Seymour, P. D. "Graph
Minors III: Planar Tree-Width." J. Combin. Th., Ser. B 36, 49-64,
1984.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Tree Decomposition." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TreeDecomposition.html