(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.
Generalization (I am a kind of ...)
cycle.
Specialization (... is a kind of me.)
traveling salesman.
See also Hamiltonian path, Euler cycle, 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.
Author: PEB
Pablo Moscato's Hamiltonian Page with papers on many aspects of Hamiltonian cycles and paths.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 10 November 2008.
HTML page formatted Wed Feb 4 11:02:22 2009.
Cite this as:
Paul E. Black, "Hamiltonian cycle", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 10 November 2008. (accessed TODAY)
Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/hamiltonianCycle.html
