= Constraint graph
For a binary <constraint satisfaction problem>, the <undirected graph> with one <vertex> per variable and an <edge> for each variable pair sharing a <binary constraint>. Unary conditions restrict <constraint domains> but add no <edges>. A more general constraint can be represented in a primal <constraint graph> by joining every pair of variables in its scope; such <edges> do not make a genuinely many-variable constraint binary.
After restricting <constraint domains>, a <binary constraint> can become automatically satisfied for every remaining pair of values. Removing such constraints can reveal a <tree> and enable <tree-structured constraint satisfaction>.
Back to article page
