Selected topics in finite mathematics/Hamiltonian cycles

A Hamiltonian cycle on a graph is a cycle which includes every vertex exactly once.

Objectives

• Given a graph, determine if a Hamiltonian cycle exists.

Details

A Hamiltonian cycle is a cycle that uses every vertex exactly once. In general it is a difficult problem to declare whether a cycle can use every vertex exactly once or not.

There are two processes that were learned in class to solve Hamiltonian cycles. First of which is called a heuristic algorithm, which is an algorithm that finds solutions quickly and better solutions. The other is called a greedy algorithm which does not look ahead but only looks at the best option at hand.

In problems involving Hamilton circuits, there are often many seemingly equivalent routes. The most important class of problems solved via Hamilton circuits is actually when the edges connecting vertices have different weights. (For instance, it might be less expensive to travel one edge rather than a different one or perhaps the distance traveled is less.)

The Traveling Salesman Problem (TSP): On a complete weighted graph the problem of finding an optimal Hamilton Circuit is often called the Traveling Salesman Problem, or TSP for short. This problem finds the quickest and most efficient way to get across all of the vertices.