**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*)

*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 [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 [1]] ≠ 0)) then return;

}

} Until (false);

}

**Related Terms**

ADA Algorithms, NP-Complete Problems, Travelling Salesman Problem, P and NP Problems

## Leave a Reply