Hamiltonian cycles and Hamiltonian paths
A Hamiltonian path is a path that visits every vertex once and only once, except that it might (or might not) begin and end at the same vertex.
A Hamiltonian cycle is a Hamiltonian path that begins and ends on the same vertex and visits all the other vertices in the graph exactly once. A Hamiltonian cycle does not necessarily traverse every edge in the graph.
A graph is called Hamiltonian if it contains a Hamiltonian cycle.
The term Hamiltonian is derived from the name of the Irish mathematician William Rowan Hamilton who designed and marketed a puzzle whose solution essentially required finding a Hamiltonian cycle in a graph.
On the surface, a Hamiltonian cycle may seem to be very much like an Eulerian circuit, but they are actually quite different. A graph that has an Eulerian circuit may or may not also contain a Hamiltonian cycle, and vice versa.
One well-known problem involving Hamiltonian cycles is the problem of finding a minimal Hamiltonian cycle in a weighted graph. this problem is also known as the Traveling Salesperson Problem or TSP because a solution to this problem answers a question commonly asked by traveling salespeople: What is the most efficient route that I can take to visit all of my clients?
Copyright © 1999-2000 SciMathMN