![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/6/60/Hamiltonian_path.svg/langit-640px-Hamiltonian_path.svg.png&w=640&q=50)
Cammino hamiltoniano
tipologia di cammino in un grafo / Da Wikipedia, l'enciclopedia encyclopedia
Caro Wikiwand AI, Facciamo breve rispondendo semplicemente a queste domande chiave:
Puoi elencare i principali fatti e statistiche su Cammino hamiltoniano?
Riassumi questo articolo per un bambino di 10 anni
Nel campo matematico della teoria dei grafi, un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta. Determinare se questo cammino esista è un problema NP-completo. In termini rigorosi, la determinazione di un cammino hamiltoniano è la ricerca di una permutazione dei nodi tale che
per ogni
dove con E si intende l'insieme di archi del Grafo.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/6/60/Hamiltonian_path.svg/320px-Hamiltonian_path.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/9/93/%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg/640px-%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg)
Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un arco che collega l'ultimo vertice con il primo, realizzando così un ciclo che visita tutti i vertici per poi ritornare al punto di partenza.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/8/81/WilliamRowanHamilton.jpeg/220px-WilliamRowanHamilton.jpeg)
Un grafo che contenga almeno un ciclo hamiltoniano viene detto grafo hamiltoniano.
Questi particolari cammini hanno preso il nome da William Rowan Hamilton che inventò un gioco da tavolo, il puzzle di Hamilton o icosian game, che consisteva nel trovare un cammino chiuso sul bordo di un dodecaedro.