Due: Sept. 14.

The HAMILTONIAN CYCLE problem is the following: Given an undirected graph G, find a path that start and ends at the same vertex and contains every other vertex exactly once. For instance, in the graph below the path A-C-F-B-G-E-H-D-A is a Hamiltonian cycle.

HAMILTONIAN CYCLE can be solved using the following state space.

State:A path through the graph containing no vertex more than once. For example, A-D-H is a state. A-C-B-A is not a state, because it repeats A. A-H-G is not a state, because there is no edge A-H.

Successor:Let P be a state, whose last vertex is U. For each edge U--V where V is not in P, the path P,V is a successor to P. For instance, the successors to A-D-H are A-D-H-E and A-D-H-G.

Start state:Path consisting of a single vertex (it doesn't matter where you start).

Goal state:A path containing every vertex once, where the first vertex in the path is connected by an edge to the last one. (For simplicity of description, we're representing the goal state as the path minus its final closing arc, as long as that arc exists. So the cycle above is represented by the state A-C-F-B-G-E-H-D.)

A ---> AB ---> ABC ---> ABCF fail | | | |--> ABF ---> ABFC fail | | | |--> ABG ---> ABGE ---> ABGED ---> ABGEDH fail | | | | | |-> ABGEH ---> ABGEHD fail | | | |-> ABGH ---> ABGHD ---> ABGHDE fail | | | |-> ABGHE ---> ABGHED fail | |-> AC ---> ACB ---> ACBF fail | | | |-> ACBG ---> ACBGE ---> ACBGED ---> ACBGEDH fail | | | | | |-> ACBGEH ---> ACBGEHD fail | | | |-> ACBGH ---> ACBGHD ---> ACBGHDE fail | | | |-> ACBGHE ---> ACBGHED fail | |-> ACF ---> ACFB ---> ACFBG ---> ACFBGE ---> ACFBGED ---> ACFBGEDH fail | |-> ACFBGEH ---> ACFBGEHD succeed.

A ---> AB ---> ABC | | | |-> ABF | | | |-> ABG | |-> AC ---> ACB | | | |-> ACF | |-> AD ---> ADE | | | |-> ADH | |-> AF

Suppose that you are using the above state space for a graph G which has N vertices and maximal degree D. What is the depth of the state space? What is the branching factor? Give an upper bound on the size. Note: your answer to this question should be in terms of the general quantities N and D; it should NOT use the features of the graph in the picture at the top.

** Answer: ** Depth: N. Branching factor D (D-1 at all but the root,
since the outarc from a node can't be the same as the inarc.).
Upper bound: D^{N}

A

stateis any assignment of the first K vertices alphabetically to positions in the path, as long as the assignment does not place two vertices that are not connected by an edge in successive positions in the path, and does not place two vertices in the same position. For example [A->3, B->6, C->5, D->1] is a state. (Another way to write this state would be D-*-A-*-C-B-*-*). [A->3, B->6, C->5, D->4] is not a state because C and D are in sequential positions in the path but are not connected by an edge. [A->3, B->3, C->5, D->1] is not a state because B and A are in the same position. In this definition, the first and last positions are considered to be "successive" positions also, so an assignment that placed D in 1 and B in 8 would also not be a state.A

successorto state S extends S by assigning the next vertex anywhere it will fit, subject to the above two constraints. For example, the only successor to the state [A->3, B->6, C->5, D->1] is the state [A->3, B->6, C->5, D->1, E->8]. The state [A->3, B->6, C->5] has three successors: [A->3, B->6, C->5, D->1], [A->3, B->6, C->5, D->2], and [A->3, B->6, C->5, D->8].The

start stateis the empty assignment.A

goal stateis a state that assigns a position to every vertex.

Suppose that one is doing a depth-first search of this state and has reached the state [A->1, B->4, C->2]. Show how the depth-first search continues from here to the goal state.

** Answer: **

AC*B**** ---> AC*B*D** ---> AC*B*DE* ---> ACFB*DE* fail (no valid spot for G). | |-> AC*B**D* ---> AC*B*ED* ---> ACFB*ED* ---> ACFBGED* fail | |-> AC*B***D ---> AC*B*E*D ---> ACFB*E*D ---> ACFBGE*D ---> ACFBGEHD succeed.

** Answer **
Depth: N. Branching factor: N. (The second vertex --- vertex B --- can
go in every slot except 1 if there is an edge A-B and in every slot
except 1, 2, and N if there is no edge A-B.)
Obvious upper bound: N^{N}. Slightly
cleverer upper bound: The number of leaves is certainly no more than the
number of permutations on N elements, which is N!.