Problem Set 1

Assigned: Sept. 7
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.)

Problem 1

Suppose that you solve the Hamiltonian path problem on the above graph using a depth-first search. Show the part of the state space that is generated up to the point that a solution is found. Assume that the start state is the single vertex A and that the search tries possible successors in alphabetical order.

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.

Problem 2

Show the first 12 states generated in a breadth-first search of this state space.

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

Problem 3

In an undirected graph, the degree of a vertex is the number of edges that connect to it. The maximal degree of the graph is the maximum degree of any of its vertices. For instance, in the above graph, vertex A has degree 4, C has degree 3, and the graph has maximal degree 4. In many applications of graphs, the maximal degree is much less than the number of vertices.

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: DN

Problem 4

An alternative state space for Hamiltonian path is as follows:

A state is 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 successor to 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 state is the empty assignment.

A goal state is 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.


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.

Problem 5

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.

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: NN. Slightly cleverer upper bound: The number of leaves is certainly no more than the number of permutations on N elements, which is N!.