Hamiltonian Problem
Hamiltonian Problem is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.

 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 I^{th} 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)
{
Loop
Next value (k)
If (x (k)=0) then return;
{
If k=n then
Print (x)
Else
Hamiltonian (k+1);
End if
}
Repeat
}
Algorithm Nextvalue (k)
{
Repeat
{
X [k]=(X [k]+1) mod (n+1); //next vertex
If (X [k]=0) then return;
If (G [X [k1], X [k]] ≠ 0) then
{
For j=1 to k1 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 [1]] ≠ 0)) then return;
}
} Until (false);
}
Related Terms
ADA Algorithms, NPComplete Problems, Travelling Salesman Problem, P and NP Problems
Leave a Reply