Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 10 M

Year: May 2015

• In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.

• Consider the problem of a salesman who wants to visit all the cities represented as vertices in the following graph exactly once:
• For such problems we use Hamiltonian circuits.
• A path that starts at a vertex of a graph, passes through every vertex exactly once and returns to the starting vertex is called a Hamiltonian circuit/Hamiltonian cycle. For the graph given above (1, 2, 4, 3, 1) is one such circuit.
• Consider the following graph

• This graph does not have even a single Hamiltonian cycle. Hence it is not a Hamiltonian graph.
• A path that starts at a vertex of a graph, passes through every vertex exacly once and does not returns to the starting vertex is called a Hamiltonian path.
• For the graph given above (1, 4, 2, 5, 3) is one such path.
• A Hamiltonian cycle can be easily converted into Hamiltonian path by removing the last edge (or the last vertex) of the circuit.
• Consider the following weighted graph for which there are more than one Hamiltonian cycle from vertex1.

• A optimal Hamiltonian cycle for a weighted graph G is that Hamiltonian cycle which has smallest paooible sum of weights of edges on the circuit (1,2,3,4,5,6,7,1) is an optimal Hamiltonian cycle for the above graph.
• There is a problem called “Travelling Salesman Problem” in which one wants to visit all the vertices of graph G exactly once in such a way that the sum of weights of edges in the circuit should be minimum. An optimal Hamiltonian cycle is a solution to this problem.

Hamiltonian Algorithm: Given as input a simple graph G with n vertices. Label the vertices 1, 2, ..., n in descending order of degrees d(1) ≥ d(2) ≥ ... ≥ d(n). For each initial vertex u = 1, 2, ..., n in turn, perform Parts I, II and III as follows:

• Part I:

  • Initialization: Select the vertex v1 = u and let the path of visited vertices be v1.
  • Iteration: Let the last selected vertex be vr and the path of visited vertices be v1, ..., vr. For each unvisited neighbor w of vr, compute η(w), the number of unvisited neighbors of w. Select vr+1 = w such that η(w) is a minimum (if there are many possible choices, select w with the smallest label). Extend the path of visited vertices to v1, ..., vr, vr+1.
  • Termination: Iterate until the last selected vertex has no unvisited neighbors.
  • Result: A path P(0) visiting vertices u = v1, ..., vk(0) such that vk(0) has no unvisited neighbors.

• Part II: Using the result of Part I,

  • (a) If k(0) < n:

    • If there is a vertex vi in P(0) such that vi is a neighbor of vk(0) and vi+1 has a neighbor w outside P(0):
    • Initialization: For each vi in P(0) such that vi is a neighbor of vk(0) and vi+1 has a neighbor w outside P(0), and for each such neighbor w, compute η(w), the number of unvisited neighbors of w. Choose vi and w0 = w such that η(w) is a maximum (if there are many possible choices, choose the one where w has the smallest label). Reorder the path of visited vertices to be u = v1, ..., vi-1, vi, vk(0), vk(0)-1, ..., vi+1 and rename the visited vertices u = v1, ..., vk(0) in this order. Select the vertex vk(0)+1 = w0 and let the path of visited vertices be v1, ..., vk(0)+1. Now perform iterations exactly as in Part I to extend the path of visited vertices to u = v1, ..., vk(1) such that vk(1) has no unvisited neighbors. Call this path P(1).
    • Iteration: Let the last computed path be P(s) with visited vertices u = v1, ..., vk(s). For each vi in P(s) such that vi is a neighbor of vk(s) and vi+1has a neighbor w outside P(s), and for each such neighbor w, compute η(w), the number of unvisited neighbors of w. Choose vi and ws = w such that η(w) is a maximum (if there are many possible choices, choose the one where w has the largest label). Reorder the path of visited vertices to be u = v1, ..., vi-1, vi, vk(s), vk(s)-1, ..., vi+1 and rename the visited vertices u = v1, ..., vk(s) in this order. Select the vertex vk(s)+1 = ws and let the path of visited vertices be v1, ..., vk(s)+1. Now perform iterations exactly as in Part I to extend the path of visited vertices to u = v1, ..., vk(s+1)such that vk(s+1) has no unvisited neighbors. Call this path P(s+1).
    • Termination: Iterate until the last selected path P(s) with visited vertices u = v1, ..., vk(s) has no vertex vi such that vi is a neighbor of vk(s) andvi+1 has a neighbor ws outside P (s).

  • Result: A path P(s) with visited vertices u = v1, ..., vk(s) such that:

    • (i) P(s) has no vertex vi such that vi is a neighbor of vk(s) and vi+1 has a neighbor ws outside P(s).
    • (ii) The vertex vk(s) has no unvisited neighbors.
  • (b) If k(s) < n:
    • Try to further extend the path P(s) by finding viin the subpath v1, ..., vk(s)-2 such that vi has a neighbor w1 outside P(s). Now try to find a path w1, w2, ...,wm amongst the unvisited vertices by a procedure similar to Part I. Trim the path from the right, if necessary, so that wm has a neighbor vj such thati+1 < j < k(s) and vi+1 is a neighbor of vj+1. If successful, we obtain the extended path v1, ..., vi, w1, w2, ...,wm, vj, vj-1, ..., vi+1, vj+1, vj+2, ..., vk(s). Repeat this procedure as long as we obtain an extended path. Reassign s and the extended path P(s) with visited vertices u = v1, ..., vk(s).
  • (c) If k(s) < n:
    • Repeat the above procedure (b) for the reversed path P(s) with visited vertices vk(s), vk(s)-1, ..., v1.

• Part III: Using the result of Part II,

  • If k(s) < n:
    • Output: Found path v1, ..., vk(s).
  • If k(s) = n:
    • (i) Output: Found Hamiltonian tour v1, ..., vn.
    • (ii) Define X = {vi | v1vi+1∈E} and Y = {vi | vivn∈E}. If X∩Y ≠ ∅, then for each vi∈X∩Y :
    • Output: Found Hamiltonian circuit v1, ..., vi-1, vi, vn, vn-1, ..., vi+1.