NIST

Hamiltonian cycle

(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: A Hamiltonian cycle includes each vertex once; an Euler cycle includes each edge once.

Also known as a Hamiltonian circuit.

Named for Sir William Rowan Hamilton (1805-1865).

Author: PEB

Implementation

(Fortran, C, Mathematica, and C++)
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 September 2014.
HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:
Paul E. Black, "Hamiltonian cycle", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/hamiltonianCycle.html