Hamiltonian cycle

The Hamiltonian path is the path that visits every vertex exactly once in an undirected graph. And the Hamiltonian cycle is a Hamiltonian path that has an edge from the last vertex to the first vertex. The Hamiltonian cycle is also known as the Hamiltonian circuit. It is named after Sir William Rowan Hamilton. He devised a puzzle, known as the icosian game, in this puzzle the path along the polyhedron edges of a dodecahedron was sought. 

Input for the Hamiltonian graph can either be directed or undirected graph. 

In the Hamiltonian problem we check if the Hamiltonian cycle is present in the graph or not. 

To generate a space tree we keep in mind the following restrictions:

1. The ith vertex in the path must be next to the (i-1)th vertex in any path. 
2. The first vertex in the graph and the (n-1)th vertex must be adjacent to each other. 
3. The ith vertex cannot be the first in the (i-1)th vertex in the path. 

The Hamiltonian cycle problem has many applications. It helps in time scheduling, and the choice of travel routes and network topology. It also plays an important role in other areas such as graph theory, algorithm design, and computational complexity. 

Dirac’s theorem tells us that a simple graph with n vertices in which each vertex has degree of [n/2] has a Hamiltonian cycle. 

Ore’s theorem tells us that a simple graph with n vertices in which the sum of the degrees of two non-adjacent vertices is greater than or equal to n has a Hamiltonian cycle. 

To find the Hamiltonian cycle, we must choose the edges that forms the cycle, in order to avoid the extra edges. The edges that are not a part of the Hamiltonian cycle must be deleted. 

A deletion of graph is a random way of removing edges that are not incident to the vertices of the graph. We keep repeating the process unti; we cannot delete anymore. 

We refer to the deleted edges as surplus edges. 

The algorithm is as follows:

Input: a graph G(V, E)
Output: a graph G’ without any surplus edges. 
Deletion (G)
{ for each vertex v in V
For each edge e incident to v
If e is a surplus edge
Remove “e”.
} 

There can be two approaches to solving the Hamiltonian cycle problem:

1. The naive approach

In this we generate all the possible configurations of the vertices and print a configuration that will satisfy the requirements. So there will be n! possible configurations. 

2. The backtracking algorithm

In this we create an empty path array and add a vertex to it. Then we keep adding more vertices after checking if its adjacent to the previous added vertices. We also check if its already added or not, if it is already added we add it as a part of the solution. 

Reference

Hamiltonian cycle