5. Hamiltonian Graphs

In 1855 Thomas P. Kirkman posed the following question: Given the graph of a polyhedron, can one always find a circuit that passes through each vertex once and only once? Two years later Sir William Rowan Hamilton gave a lecture at the Royal Society on the construction of cycles containing all vertices in the graph of the dodecahedron. The name of the „Hamiltonian Cycle" based on this story. (It was the "Rubik cube " of the 19. century.)

In fact, Hamilton cycles and paths in special graphs had been studied long before Hamilton proposed his game. The puzzle of the knight`s tour on a chessboard, thoroughly analysed by Euler in 1759, ask for a Hamilton cycle in the graph whose vertices are the 64 squares of a chessboard and in which two vertices are adjacent if a knight can jump from one square to the other.

The original problem - and ist solution - is presented on the next figure.

 

 

 Figure 5.1. A hamiltonian cycle in a dodecahedron

A variant of the original problem from the 20-th century ist he so-called traveling salesman problem: a salesman is to make a tour of n cities, at the end of which he has to return to the head office he starts from. The cost of the journey between any two cities is known. The problem asks for an efficient algorithm for finding a least expensive tour.

If the route is required to be a cycle, which is the salesman is not allowed to visit the same city twice, so we are looking for a hamiltonian cycle.