0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

An Algorithm to solve
the Hamiltonian Cycle problem!

Some basic terminology

Frequently Asked Questions

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>

Twitter GitHub