- To find a Hamiltonian cycle un graph ‘G’ is not a decision problem but is graph G Hamiltonian is a decision problem.
- In Hamiltonian problem graph G is accepted as input and it is asked to find a simple cycle in G that visits each vertex of G exactly on and returns to its starting vertex. Such a cycle is called Hamiltonian cycle.
- Let G= (V, E) be a connected graph with ‘n’ vertices. A HAMILTONIAN CYCLE is a round trip path along ‘n’ edges of G which every vertex once and returns to its starting position.
- If the Hamiltonian cycle begins at some vertex V1 belongs to G and the vertex are visited in the order of V1, V2….
- .Vn+1, then the edges are in E,1<=I<=n and the Vi are distinct except V1 and Vn+1 which are equal.
Consider an example graph G1.
The graph G1 has Hamiltonian cycles: ->1, 3, 4, 5, 6, 7, 8, 2, 1 and ->1, 2, 8, 7, 6, 5, 4, 3, 1.
The backtracking algorithm helps to find Hamiltonian cycle for any type of graph.
Procedure for Hamiltonian Problem
- Define a solution vector X(Xi……..Xn) where Xi represents the Ith visited vertex of the proposed cycle.
- Create a cost adjacency matrix for the given graph.
- The solution array initialized to all zeros except X (1) =1, because the cycle should start at vertex ‘1’.
- Now we have to find the second vertex to visited in the cycle.
- The vertex from 1 to n are included in the cycle one by one by checking 2 conditions,
- There should be a path from the previously visited vertex to current vertex.
- The current vertex must be distinct and should not have visited earlier.
- When these two conditions satisfied the current vertex included in the cycle, else the next vertex tried.
- When the nth vertex visited we have to check, is there any path from the nth vertex to first 8 vertexes. If no path, then go back one step and after the previously visited node.
- Repeat the above steps to generate possible Hamiltonian cycle.
Algorithm:(Finding all Hamiltonian cycle)
Algorithm Hamiltonian (k)
Next value (k)
If (x (k)=0) then return;
If k=n then
Algorithm Nextvalue (k)
X [k]=(X [k]+1) mod (n+1); //next vertex
If (X [k]=0) then return;
If (G [X [k-1], X [k]] ≠ 0) then
For j=1 to k-1 do if (X [j] =X [k]) then break; // Check for distinction.
If (j=k) then //if true then the vertex is distinct.
If ((k<n) or ((k=n) and G [X [n], X ] ≠ 0)) then return;
} Until (false);