Editing Hamiltonian path (section)

{{short description|Path in a graph that visits each vertex exactly once}}
{{about|the nature of Hamiltonian paths|the question of the existence of a Hamiltonian path or cycle in a given graph|Hamiltonian path problem}}
[[File:Hamiltonian.png|thumb|A Hamiltonian cycle around a network of six vertices]]
[[File:Натурализация гамильтоновых циклов.jpg|thumb|Examples of Hamiltonian cycles on a square grid graph 8x8]]
In the [[mathematics|mathematical]] field of [[graph theory]], a '''Hamiltonian path''' (or '''traceable path''') is a [[path (graph theory)|path]] in an undirected or directed graph that visits each [[vertex (graph theory)|vertex]] exactly once. A '''Hamiltonian cycle''' (or '''Hamiltonian circuit''') is a [[cycle (graph theory)|cycle]] that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are [[NP-complete]]; see [[Hamiltonian path problem]] for details.

Hamiltonian paths and cycles are named after [[William Rowan Hamilton]], who invented the [[icosian game]], now also known as ''Hamilton's puzzle'', which involves finding a Hamiltonian cycle in the edge graph of the [[dodecahedron]].  Hamilton solved this problem using the [[icosian calculus]], an [[algebraic structure]] based on [[root of unity|roots of unity]] with many similarities to the [[quaternion]]s (also invented by Hamilton).  This solution does not generalize to arbitrary graphs.

Despite being named after Hamilton, Hamiltonian cycles in polyhedra had also been studied a year earlier by [[Thomas Kirkman]], who, in particular, gave an example of a polyhedron without Hamiltonian cycles.<ref>{{citation
 | last = Biggs | first = N. L.
 | doi = 10.1112/blms/13.2.97
 | issue = 2
 | journal = The Bulletin of the London Mathematical Society
 | mr = 608093
 | pages = 97–120
 | title = T. P. Kirkman, mathematician
 | volume = 13
 | year = 1981}}.</ref> Even earlier, Hamiltonian cycles and paths in the [[knight's graph]] of the [[chessboard]], the [[knight's tour]], had been studied in the 9th century in [[Indian mathematics]] by [[Rudrata]], and around the same time in [[Mathematics in medieval Islam|Islamic mathematics]] by [[al-Adli ar-Rumi]]. In 18th century Europe, knight's tours were published by [[Abraham de Moivre]] and [[Leonhard Euler]].<ref>{{citation|title=Across the Board: The Mathematics of Chessboard Problems | first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|pages=25–38|chapter=Chapter 2: Knight's Tours | isbn=978-0-691-15498-5}}.</ref>