HAMILTONIAN CYCLE

Domain	Definition
Computing	Hamiltonian cycle Hamiltonian problem. Source: The Free On-line Dictionary of Computing.
Math	A path through a graph which starts and ends at the same vertex and includes every other vertex exactly once. (references)
Source: compiled by the editor from various references; see credits.

Specialty Definition: Hamiltonian cycle problem

The Hamiltonian cycle or Hamiltonian circuit problem in graph theory is to find a path through a given graph which starts and ends at the same vertex and includes each vertex exactly once.

It is a special case of the traveling salesman problem, obtained by setting the distance between two cities to unity if they are adjacent and infinity otherwise. Like the traveling salesman problem, the Hamiltonian cycle problem is NP-complete.

The requirement that the path start and end at the same vertex distinguishes it from the Hamiltonian path problem.

The problem is named after Sir William Rowan Hamilton.

See also: Hamiltonian path

External links

Hamiltonian circuit - Mathworld

Anagrams: HAMILTONIAN CYCLE

Scrabble® Enable2K-Verified Anagrams
	Words within the letters "a-a-c-c-e-h-i-i-l-l-m-n-n-o-t-y"
	-3 letters: cinematically, collenchymata.
	-4 letters: cancellation, cationically, mechanically, melancholiac.
	-5 letters: acclimation, actinically, actinomycin, anticyclone, calcination, cancelation, canonically, chaotically, collenchyma, homiletical, inanimately, machination, mechanician, meiotically, melancholia, melancholic, nonchemical, nonmetallic, technically.
Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro.