Consider the following subgraph isomorphism problem. The binary relation F
has the following pairs: F={(1,3)(1,4)(2,1)(3,2)(4,3)(4,5)}.
The binary relation G has the following pairs:
G={((A,C)(A,D)(B,A)(C,B)(C,F)(D,C)(D,E)(F,E)}. We want to find a subgraph
isomorphism (like on CSP lecture slide 15) from the variables {1,2,3,4,5}
to the values {A,B,C,D,E,F}. The constraint relation R is given by:
R = {(i,v,j,v') | if (i,j) is in F then (v,v') must be in G
and if (j,i) is in F then (v',v) must be in G}
This says that if i and j are connected by an edge in relation F,
v and v' must be connected by the edge (in the appropriate direction) in
relation G.
- First draw the 2 graphs F and G.
- Then show the specified parts of the tree search to
find a consistent labeling using only forward checking and
none of the other heuristics. Do this in the blind order that
has variable 1 at level 1 in the tree, variable 2 at level 2,
and so on all the say down to variable 5 at level 5. At each level,
of the values that are still possible, try them in alphabetical order.
- Start the search at node (1,A). Apply forward checking and show
the whole FTAB for variables 2, 3, 4, and 5. Do the same for the
whole subtree under (1,A). If you find any consistent labelings
mark them with a *.
- Do the same for (1,B).
- So for every node you show of the tree search, you show the
assignment at that node and a forward checking table at all levels
except level 5 where there are no more future units.
- The subtrees below (1,A) and (1,B) are all you have to do.
You don't need to go any further unless you're curious.
