| Ricerca | Nodi | Risultato |
|---|---|---|
| Backtracking semplice | – | – |
| Ordine di Warnsdorff | – | – |
| Controlli di vicolo cieco e connessione | – | – |
| Tutti e tre | – | – |
Esploratore di cammini hamiltoniani
Nel 1857 William Rowan Hamilton inventò un rompicapo: percorrere gli spigoli di un dodecaedro passando per ciascuno dei suoi 20 angoli esattamente una volta e finendo dove si è partiti. Un percorso così oggi si chiama ciclo hamiltoniano. È facile da verificare e, in generale, difficile da trovare. Tracciane uno tu stesso sul dodecaedro di Hamilton, su una scacchiera o su un grafo che disegni, oppure guarda una ricerca con backtracking cercarlo, conta i vicoli ciechi in cui finisce e vedi quanto pochi controlli semplici accorciano la ricerca. Scegli un grafo e un obiettivo: un ciclo che torna al punto di partenza o un cammino. Traccia: clicca su un vertice per iniziare, poi su un vicino alla volta; gli anelli tratteggiati mostrano dove puoi andare. Un clic sull'ultimo vertice, Indietro o Annulla torna di un passo, e Suggerimento indica un passo successivo che porta ancora alla fine. Ricerca: con Avvia o Passo scorre una ricerca con backtracking, che aggiunge vertici finché non si blocca e poi torna indietro; i trattini rossi mostrano i ritorni e le barre contano i nodi per ogni lunghezza del cammino. Prima dell'avvio un clic su un vertice sceglie da dove parte. Le caselle attivano e disattivano la potatura, Confronta esegue la stessa ricerca con e senza, e Conta tutti conta ogni ciclo o cammino di un grafo piccolo. Modifica: clicca per aggiungere un vertice, clicca su due vertici per unirli o separarli, trascina per spostarne uno, ed Elimina toglie il vertice selezionato.
Come funziona
- Scegli un grafo, per esempio il dodecaedro di Hamilton, il grafo di Petersen o un giro del cavallo, oppure disegna il tuo in Modifica, e scegli come obiettivo un ciclo o un cammino.
- In Traccia clicca su un vertice per iniziare e poi su un vicino dopo l'altro. Indietro e Annulla tornano di un passo, e Suggerimento mostra un passo successivo che porta ancora alla fine.
- In Ricerca premi Avvia o Passo per guardare il backtracking cercare un percorso, attiva e disattiva la potatura, e premi Confronta per vedere quanti nodi richiede ogni versione.
Hamilton contro Eulero
Un cammino euleriano usa ogni arco una volta; un cammino hamiltoniano passa per ogni vertice una volta. Suonano simili ma si comportano in modo molto diverso. Se un grafo connesso abbia un cammino euleriano si decide contando i vertici di grado dispari, come mostrò Eulero nel 1736: ne ha uno quando non ce ne sono o ce ne sono due. Per i cammini hamiltoniani non si conosce una regola simile. Decidere se un grafo ha un ciclo hamiltoniano è NP-completo, uno dei 21 problemi della lista di Richard Karp del 1972, quindi un metodo veloce per esso darebbe metodi veloci per migliaia di altri problemi difficili. Esistono invece condizioni che decidono alcuni grafi. Il teorema di Dirac del 1952 garantisce un ciclo hamiltoniano quando ogni vertice ha grado almeno n/2, e quello di Ore del 1960 quando due vertici non uniti hanno sempre gradi con somma almeno n; un vertice di grado 1, un vertice di taglio o due classi di colore di dimensioni diverse lo escludono.
Come funziona la ricerca
Il backtracking costruisce il cammino un vertice alla volta e, quando si blocca, ritira l'ultimo passo e prova il vicino successivo. Trova sempre un ciclo hamiltoniano se ce n'è uno, ma il numero di cammini parziali può crescere in modo esponenziale. Sulla griglia 5 × 5, che non ha un ciclo hamiltoniano, il backtracking semplice esplora 153.745 nodi prima di esserne certo. Due controlli fermano presto i cammini senza speranza: un vertice non visitato con meno di due vicini liberi non può più entrare in un ciclo, e quando i vertici non visitati si spezzano in parti separate, nessun singolo cammino può coprirli. Con entrambi la stessa dimostrazione richiede 1.761 nodi. La regola di Warnsdorff del 1823, che prova per primo il vicino con meno mosse successive, trova un giro del cavallo su 8 × 8 da un angolo in 64 mosse senza un solo vicolo cieco.
Domande frequenti
Qual è la differenza tra un cammino hamiltoniano e un ciclo hamiltoniano?
Un cammino hamiltoniano passa per ogni vertice di un grafo esattamente una volta. Un ciclo hamiltoniano fa lo stesso e poi torna con un arco in più al punto di partenza, quindi può iniziare da qualsiasi suo vertice. Ogni grafo con un ciclo hamiltoniano ha un cammino hamiltoniano (basta togliere un arco del ciclo), ma non viceversa: il grafo di Petersen ha cammini hamiltoniani e nessun ciclo hamiltoniano.
Il dodecaedro ha un ciclo hamiltoniano?
Sì, 30, contando ogni ciclo una volta qualunque sia la partenza e il verso. Hamilton ne fece il gioco icosiano nel 1857, una tavola con i 20 angoli di un dodecaedro appiattito segnati da consonanti, e vendette i diritti per 25 sterline al produttore di giocattoli londinese John Jaques and Son. Conta tutti trova i 30 cicli in circa 1.400 nodi.
Perché una griglia 5 × 5 non ha un ciclo hamiltoniano?
Colora i 25 punti come una scacchiera: 13 prendono un colore e 12 l'altro, e ogni passo va all'altro colore. Un ciclo alterna i colori per tutto il giro, quindi gliene servono altrettanti di uno e dell'altro, cosa che 13 e 12 non danno. Lo stesso argomento vale per ogni griglia con un numero dispari di punti, per un cavallo su una scacchiera 5 × 5 o 7 × 7 (il cavallo cambia sempre colore di casa) e per il grafo di Herschel, le cui due classi hanno 6 e 5 vertici. Un cammino hamiltoniano resta possibile: inizia e finisce sul colore più numeroso.
Come trova la regola di Warnsdorff un giro del cavallo?
H. C. von Warnsdorff propose nel 1823 di muovere sempre il cavallo sulla casa dalla quale avrà meno mosse successive. Le case vicine ai bordi e agli angoli, facili da isolare, vengono così visitate presto, finché il cavallo può ancora entrarci. La regola è empirica, non una garanzia, e i pari merito vanno sciolti in qualche modo, ma su una scacchiera 8 × 8 di solito completa un giro senza tornare indietro. Unita al backtracking, come nell'app, trova giri aperti da 5 × 5 in su e giri chiusi sulle scacchiere 6 × 6 e 8 × 8.
Quanti cicli hamiltoniani ha un grafo completo?
(n − 1)!/2 per n ≥ 3. Fissa il vertice di partenza; gli altri n − 1 possono seguire in qualsiasi ordine, e ogni ciclo viene contato due volte, una per verso. K₆ ne ha 5!/2 = 60 e K₁₀ ne ha 181.440. Sono i giri tra cui deve scegliere un commesso viaggiatore, ed è per questo che provarli tutti smette così in fretta di essere possibile.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor