Circuiti >
Un percorso Hamiltoniano, chiamato anche percorso di Hamilton, è un percorso tra due vertici di un grafico che visita ogni vertice esattamente una volta. Se esiste un percorso hamiltoniano i cui punti finali sono adiacenti, allora il ciclo del grafo risultante è chiamato ciclo hamiltoniano (o ciclo hamiltoniano).
Un grafo che possiede un percorso hamiltoniano è chiamato traceablegraph.
In generale, il problema di trovare un percorso hamiltoniano è NP-completo (Garey e Johnson 1983, pp. 199-200), quindi l’unico modo conosciuto per determinare se un dato grafo generale ha un percorso hamiltoniano è quello di intraprendere una ricerca esaustiva
Ogni grafo bipartito con uno sbilanciamento di parità dei vertici 
non ha percorsi hamiltoniani.
Trovare un singolo percorso hamiltoniano di un grafo 
è implementato nel linguaggio Wolfram come FindHamiltonianPath. Tutti i percorsi hamiltoniani di un dato grafo possono essere trovati (in modo inefficiente) usando il comando HamiltonianPath nel pacchetto Combinatorica` del linguaggio Wolfram. Una lista precalcolata di tutti i percorsi hamiltoniani per molti grafi nominati può essere ottenuta usando GraphData, dove e entrambi gli orientamenti dei percorsi sono inclusi (in modo che 
è considerato distinto da 
). Un conteggio precalcolato del corrispondente numero di cammini hamiltoniani è dato da GraphData.
I numeri totali di cammini hamiltoniani diretti per tutti i grafi semplici di ordine 
, 2, … sono 0, 2, 8, 50, 416, 5616, 117308, 4862736, … (OEIS A193352).
Rubin (1974) descrive una procedura di ricerca efficiente che può trovare alcuni o tutti i percorsi e circuiti Hamilton in un grafo usando deduzioni che riducono notevolmente il backtracking e le congetture. Un algoritmo probabilistico dovuto ad Angluin e Valiant (1979), descritto da Wilf (1994), può anche essere utile per trovare cicli e percorsi hamiltoniani. Un percorso hamiltoniano tra due vertici 
e 
può essere trovato se è disponibile un algoritmo per i cicli hamiltoniani. Questo può essere fatto controllando se il grafico originale 
contiene il bordo 
e aggiungendolo in caso contrario per ottenere 
. Poiché un percorso hamiltoniano con punti finali adiacenti è un ciclo hamiltoniano e poiché 
e 
sono ora adiacenti, trovando un ciclo hamiltoniano e dividendo il bordo si ottiene un percorso hamiltoniano da 
a 
in 
. Allo stesso modo, se non esiste un ciclo hamiltoniano in 
, allora non esiste un percorso hamiltoniano da 
a 
in 
.
La seguente tabella riassume i numeri di percorsi hamiltoniani (non diretti) su varie classi di grafi.
| grafo | formula |
| grafo a bilanciere |  |
grafico del cocktail party  |
 |
grafico completo  |
 |
grafo bipartito completo  |
 |
 grafo a prisma incrociato |
 |
grafico del ciclo  |
 |
| grafico del cambio grafico |  |
grafico ladder  |
 |
Scala di Möbius  |
 |
percorso grafico  |
1 |
grafico del prisma  |
 |
| grafico del sole |  |
grafico della ruota  |
 |
Le relazioni di ricorrenza per il numero di percorsi hamiltoniani diretti per alcune famiglie di grafi sono riassunte di seguito.
| graph | order | recurrence |
| grafico antiprisma | 9 |  |
| grafico a corona | 3 |  |
grafico del prisma  |
6 |  |