Suppose we have variable *X* and *Y*. A relation *r(X,Y)* is converted
into two arcs *<X,r(X,Y)>* and *<Y,r(X,Y)>*.
The arc *<X,r(X,Y)>* is **arc consistent** if for every element of the
domain of *X*, there is an element of the domain of *Y* such that
*r(X,Y)* is true. It can be made arc consistent by removing those elements
of the domain of *X* for which there is no corresponding element of
the domain of *Y*.

For example, suppose we have variables *A* and *B* with domains
*{1,2,3,4}* and the relation *A<B*. This can be drawn as a network:

Neither arc is arc consistent. You can click on the left-hand
arc (the *<A,(A<B)>* arc) to make it arc consistent. Note how the
domain of *A* is reduced and the arc turns green. You can click on the
right-hand arc (the *<B,(A<B)>* arc) to make it arc consistent. The
domain of *B* is reduced and the arc turns green. At this stage all
arcs are arc consistent, and we say that the network is arc
consistent.

In this and the following networks the green arcs are those arcs that
are known to be arc consisitent. The blue arcs are those that are not
known to be arc consistent. Clicking on a blue arc *<X,r(X,Y)>* makes it arc
consistent by perhaps reducing the domain of *X*. You can
reset
the network to see how this works.

Once an arc *<X,r(X.Y)>* has been made arc consistent, it will
remain arc consistent until the domain of *Y* is reduced. When the
domain of *Y* is reduced, the arc will become blue. This means that the
arc needs to be checked; it does not mean that the arc is necessarily
not arc consistent.

Consider the following example with four arcs:

If you click the arcs from left to right, notice how they all become
green when clicked. However, when the third arc is clicked, the
*<A,(A<B)>* arc becomes blue, as the domain of *B* has been reduced.
You can
reset
the network to see it again.

Artificial Intelligence online material, ©David Poole and Alan Mackworth, 2008