(definition)
Definition: A path through a graph that starts and ends at the same vertex and includes every other vertex exactly once.
Also known as tour.
See also cycle, traveling salesman, Euler cycle, simple path, vehicle routing problem, perfect matching.
Note: Named for Sir William Rowan Hamilton (1805-1865) (a longer biography). A Hamiltonian cycle includes each vertex once; an Euler cycle includes each edge once.
Also known as a Hamiltonian circuit. Ignoring the start (or end) vertex, a Hamiltonian cycle is a simple path.
Author: PEB
Links to papers on every aspect of Hamiltonian cycles and paths.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 11:52:19 2004.
HTML page formatted Wed Oct 26 09:47:35 2005.
Cite this as:
Paul E. Black, "Hamiltonian cycle", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/hamiltonianCycle.html
