Constraint Propagation Example Graph Coloring R G. B Different-color constraint Initial Domains Arc examined Value deleted R, 2, B none V1>V2 V1(G) R G G Arcs to examine V,<Vo,V-V F An element of a variables domain is removed THEN add all arcs to that variable to the examination queue. Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted non V>V V,(G) Arcs to examine V,<Va,V2-V3,V2>V,yV IF An element of a variables domain is removed THEN add all arcs to that variable to the examination queue.15 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V1 V (G) 1>V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1<V3, V2-V3 IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue. 16 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V1 V (G) 1>V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1<V3, V2-V3, V2>V1, V1<V3, IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue