Content deleted Content added
→Tree decomposition: solving algorithm |
→Join-tree clustering: example with images |
||
Line 69:
Conformality is enforced by replacing all initial constraints with new ones. In particular, for every maximal clique of the graph resulting from enforcing chordality, a new constraint with the clique as scope is created. The satisfying values of this new constraint are the ones satisfying all original constraints whose scope is contained in the clique.
{| cellpadding=20 style="border: thin gray solid;"
|-
| [[Image:Join-tree-clustering-1.svg]]
| [[Image:Join-tree-clustering-2.svg]]
| [[Image:Join-tree-clustering-3.svg]]
|-
| An example: a binary constraint satisfaction problem (join-tree clustering can also be applied to non-binary constraints.) This graph is not chordal (x3x4x5x6 form a cycle of four nodes having no chord).
| The graph is made chordal. The algorithm analyzes the nodes from x6 to x1. The red edge is the only edge added because x6 is the only node having two non-joined parents. It represents a constraint between x4 and x5 that is satisfied by every pair of values.
| The maximal cliques of the resulting graph are identified. Join-tree clustering replaces the constraints on {x3, x4, x5, x6} with two equivalent constraints, one on {x3, x4, x5} and one on {x4, x5, x6}.
|}
By this transformation, every original constraint is "included" in at least one new constraint. Indeed, the scope of every original constraint is a clique of the primal graph. This clique remains a clique even after enforcing chordality, as this process only introduces new edges. As a result, this clique either is maximal or is contained in a maximal clique.
| |||