Junction tree
From Wikipedia, the free encyclopedia
Junction trees are a concept from graph theory that play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. Junction trees are sometimes called clique trees or join trees.
A junction tree is a tree T whose nodes and edges are annotated with sets of vertices from an undirected graph G. The vertex set associated with a junction tree node is called the node's clique (even though it need not be a clique of G). The vertex set associated with a junction tree edge is called the edge's separator, and it is defined to be the intersection of the two incident nodes' cliques.
A valid junction tree T for an undirected graph G satisfies two properties:
- every clique of G is contained in some clique of T; and
- the cliques of T satisfy the running intersection property: for each node v of G, the cliques and separators containing v form a connected subtree of T.
An alternative characterization of the running intersection property is this:
- for each pair of nodes in the junction tree T, the intersection of their cliques is contained in all cliques (and separators) on the unique path between them in T.
 |
|
[edit] Construction of junction trees
Given an undirected graph G, a junction tree T for G can be constructed as follows:
- Run the elimination algorithm on G to compute a set of elimination cliques
. - Construct a weighted, complete, undirected graph whose nodes are the elimination cliques . Set the weight on each edge to the negative size of the intersection of the two incident elimination cliques.
- Compute a minimum spanning tree T for this graph.
Then T is a junction tree for G.
