Metraipolis › archive › dc_aa841ae417af
Hamiltonian path — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Hamiltonian_path
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T16:17:27.230Z
- SHA-256 of the archived text
4eab3c82e9b4e2ae5b7410d04d4bbf0cf8b2c47b184c0d5fdbf0037fc76c41cc- Stable URL of this page
https://metraipolis.com/documento/dc_aa841ae417af
How to cite
Hamiltonian path — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Hamiltonian_path (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_aa841ae417af (Metraipolis archive dc_aa841ae417af, sha256 4eab3c82e9b4e2ae5b7410d04d4bbf0cf8b2c47b184c0d5fdbf0037fc76c41cc)
BibTeX
@misc{dcaa841ae417af,
title = {Hamiltonian path — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Hamiltonian_path},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_aa841ae417af; sha256 4eab3c82e9b4e2ae5b7410d04d4bbf0cf8b2c47b184c0d5fdbf0037fc76c41cc},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Hamiltonian_path. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a 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 roots of unity with many similarities to the quaternions (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. 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 Islamic mathematics by al-Adli ar-Rumi. In 18th century Europe, knight's tours were published by Abraham de Moivre and Leonhard Euler. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»). Fonte: Wikipedia in inglese, voce «Hamiltonian path» — https://en.wikipedia.org/wiki/Hamiltonian_path Wikidata Q273037 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q273037 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Hamiltonian_path?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1361551365, consultata il 2026-10-07T15:50:37.108Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a31bb85c1e4e1448bceee6578cac195f4322548e1bf0ae8f589ddd5b29d9a601