AI: Problem Set 1

Assigned: Jan. 22
Due: Feb. 5

Let G1 and G2 be two undirected graphs with the same number of vertices. G1 and G2 are said to be isomorphic if there is a one-to-one correspondence f(V) between the vertices of G1 and the vertices of G2 such that there is an arc from f(U) to f(V) in G2 if and only if there is an arc from U to V in G1. For instance, in Figure 1, GA is isomorphic to GB under the mapping f(A)=M, f(B)=L, f(C) = R, f(D)=Q, f(E)=J, f(F)=K, f(G)=N, f(H)=P.

Figure 1

Problem 1

The GRAPH ISOMORPHISM problem is the problem of determining whether two specified graphs are isomorphic. (This problem is not known to be solvable in polynomial time, nor is it known to be NP-complete.)

Consider the following state space for solving graph isomorphism:

• A state is a triple < K, W1, M > such that
• 1.a: K is between 0 and N, the number of vertices in G1.
• 1.b: W1 is the set of the first K vertices in G1, listed alphabetically.
• 1.c: M is a mapping from W1 to the vertices of G2 such that, for any U and V in W1, there is an edge connecting M(U) to M(V) in G2 if and only if there is an edge connecting U to V in G1.
• A operator on < K, W1, M > generates a successor state < Ka, W1a, Ma >, where
• 2.a: Ka = K+1;
• 2.b: W1a is the first K+1 vertices in G1,
• 2.c: Ma extends M by mapping the last vertex in W1a to a vertex in G2 in such a way that the condition in (1.c) is satisfied.
• The start state is < 0, empty, empty >.
• A goal state is any state whose first element is N

A. Draw the above state space where G1 and G2 are the graphs shown in figure 2.

Figure 2

B. In the general case of two graphs with N vertices, what is the depth of the state space? What is the maximum branching factor? Give an upper bound on the size of the state space. Your answer should be in terms of N, not in terms of the particular features of the graphs pictured here.

Problem 2

Modify the definition of the state space in problem 1 by adding the condition that, for any vertex U, M(U) has the same degree as U. (The degree of a vertex V is the total number of edges attached to it.)

A. Show this new state space where G1 and G2 are the graphs shown in figure 2.

B. Suppose that the state space is generated by a depth-first search, where candidates for matching a given vertex are explored in increasing alphabetical order. Show the segment of the state space generated in matching the two graphs shown in figure 1.

Problem 3

Consider the following definition of a state: A state is any one-to-one mapping of the vertices of G1 onto the vertices of G2. For instance, for the graphs in figure 1, the mapping A -> R, B -> Q, C -> P, D -> N, E -> M, F -> L, G -> K, H -> J is one state. The cost of a state is the number of edges in G1 that do not correspond to G2, plus the number of edges in G2 that do not correspond to G1.

A. What is the cost of the above mapping?

B. Propose a class of operators that would be plausible for using a hill-climbing style search over the above state space.