Introduction

A Hamiltonian cycle in a graph is a closed path that visits each vertex of the graph exactly once. The problem of determining whether a given graph contains a Hamiltonian cycle is called the Hamiltonian cycle problem. This problem is of great importance in computer science, particularly in the field of optimization and graph theory.

In this article, we will discuss the Hamiltonian cycle problem, its real-world applications, and how to solve it using backtracking algorithm in Python.

Real-World Examples and Scenarios

Hamiltonian cycles have practical applications in various fields like:

1. Traveling Salesman Problem (TSP): A salesman has to visit a number of cities and return to the starting city while minimizing the total distance traveled.
2. Sequencing problems: In DNA sequencing, Hamiltonian cycles can be used to find the shortest common superstring of a set of strings.
3. Networking: In network routing, Hamiltonian cycles can be used to find optimal routes that minimize the total cost of visiting all nodes in a network.

Real-World Scenario: Traveling Salesman Problem

Let's consider the Traveling Salesman Problem (TSP). In this problem, a salesman has to visit a number of cities and return to the starting city while minimizing the total distance traveled. The TSP can be represented as a graph where the cities are the vertices, and the edges represent the distances between the cities.

Problem Statement

Given a graph with N vertices and a starting vertex, determine if there exists a Hamiltonian cycle in the graph, and if so, find one such cycle.

Solution: Backtracking Algorithm

We can solve the Hamiltonian cycle problem using a backtracking algorithm. The basic idea of the backtracking algorithm is to construct a solution incrementally and backtrack whenever the current solution cannot be extended to a complete solution.

Here's the step-by-step process to find a Hamiltonian cycle in a graph using the backtracking algorithm:

1. Start with an empty path and push the starting vertex into it.
2. Add vertices to the path one by one, ensuring that each added vertex is adjacent to the previously added vertex and not already in the path.
3. If the path contains all vertices and the last added vertex is adjacent to the starting vertex, a Hamiltonian cycle is found.
4. If the path cannot be extended further, backtrack by removing the last added vertex and trying the next adjacent vertex.

Python Code Solution

def is_valid(v, pos, path, graph):
    # Check if vertex v is adjacent to the previously added vertex in the path
    if graph[path[pos-1]][v] == 0:
        return False

    # Check if vertex v is already in the path
    if v in path:
        return False

    return True

def hamiltonian_cycle_util(graph, path, pos):
    # Base case: If the path contains all vertices and forms a cycle
    if pos == len(graph):
        if graph[path[pos-1]][path[0]] == 1:
            return True
        return False

    # Try adding each vertex to the path
    for v in range(1, len(graph)):
        if is_valid(v, pos, path, graph):
            path[pos] = v

            if hamiltonian_cycle_util(graph, path, pos + 1):
                return True

            # Backtrack: Remove the vertex from the path
            path[pos] = -1

    return False

def hamiltonian_cycle(graph, start_vertex):
    path = [-1] * len(graph)
    path[0] = start_vertex

    if not hamiltonian_cycle_util(graph, path, 1):
        print("No Hamiltonian Cycle exists.")
    else:
        print("Hamiltonian Cycle:", path)

Example

Let's consider the following graph representing the distances between 5 cities:

graph = [
    [0, 1, 1, 0, 1],
    [1, 0, 1, 1, 1],
    [1, 1, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0]
]

We can call the hamiltonian_cycle function with this graph and the starting city as follows:

start_vertex = 0
hamiltonian_cycle(graph, start_vertex)

Output:

Hamiltonian Cycle: [0, 1, 2, 3, 4]

Explanation

The backtracking algorithm starts with an empty path and adds vertices to the path incrementally, ensuring that each added vertex is adjacent to the previously added vertex and not already in the path. When a complete Hamiltonian cycle is found, the algorithm returns the cycle. The backtracking allows the algorithm to explore all possible combinations of vertices in the graph, ensuring that if there is a Hamiltonian cycle, it will be found.

Conclusion

In this article, we have discussed the Hamiltonian cycle problem, its real-world applications, and how to solve it using the backtracking algorithm in Python. The backtracking algorithm is a powerful technique for solving combinatorial problems like the Hamiltonian cycle problem.

The solution presented here can be easily adapted to solve other similar real-world problems, such as finding the shortest common superstring in DNA sequencing and finding optimal routes in network routing.