# An Algorithm to solvethe Hamiltonian Cycle problem!

Some basic terminology

### Q: What is an algorithm?

A: An algorithm is a method, or recipe for how to do/make something. In Software, an algorithm is a set of rules or logical steps to be followed to go from a problem to its solution.

### Q: What is the Hamilton Cycle problem?

A: The Hamiltonian Cycle problem asks whether a given graph contains a Hamiltonian Cycle.

### Q: What is a graph?

A: In Graph Theory, a graph is a mathematical model representing pairwise relationships between mathematical objects. For example, let's consider a road map. The road map would have any number of cities, and then some roads connecting the cities. Each of these cities corresponds to a vertex in the graph. Each road corresponds to an edge in the graph. Note that the vertices have no fixed layout to arrange them on a plane, and the edges have no geometrical properties. We could very well be describing airports and flights. In Graph Theory, we are interested in pairwise properties between the airports; meaning, given two airports, is there a direct flight between them? If so, how long does the flight take? And how much will it cost to get from airport ABC to airport DEF?

### Q: What is a Hamiltonian Cycle?

A: To quote from WolframAlpha:

"A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once. A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph."

In other words, if starting out from city X, it is possible to visit all cities in the map ( visiting each city once, and only once ), and return to city X, then the graph is said to be Hamiltonian.

### Q: Why is it called a Hamiltonian Cycle?

A: The Hamiltonian cycle is named after Sir William Rowan Hamilton, who devised a puzzle in which such a path along the polyhedron edges of an dodecahedron was sought (the Icosian game).

Here are some graphs to get you started:
• simple graph
• bigger graph
• a non-Hamiltonian graph
• The Herschel Graph is richly connected; all vertices have degree 3 or 4. One would intuitively expect the Herschel Graph to be Hamiltonian. However, the Herschel Graph is the smallest, non-Hamiltonian, polyhedral graph.
• A 40 vertex graph that is found to be Hamiltonian rather quickly.
• The algorithm can quickly find a Knight's Tour on a chessboard with cells labelled 1-8. So vertex 11 means cell ( x=1,y=1 ); vertex 23 means cell ( x=2,y=3 ), and so on. The Knight's Tour is represented by an ordered list of vertices which form a Hamiltonian Cycle.

© 2021 Ashwin Dixit <ashwin at ownlifeful dot com>