In graph theory
, a Hamilton circuit
is a path
through a graph that visits each vertex
in the graph
exactly once, and ends at the beginning vertex. The concept of the Hamilton circuit comes from a puzzle invented in 1857 by the Irish mathematician Sir William Rowan Hamilton
. Hamilton's puzzle consisted of a wooden dodecahedron
with a peg at each vertex of the dodecahedron, and string. The 20 verticies of the dodecahedron were labeled with different cities in the world. The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the first city. The circuit traveled was marked off using the stings and pegs.
The problem of finding a Hamilton circuit in a given graph is considered to be NP-Complete.
Source: Discrete Mathematics and Its Applications