Cammini e cicli hamiltoniani spiegati

Disegna cinque punti in cerchio, unisci ciascuno ai suoi due vicini, e puoi fare il giro passando una volta per ogni punto e tornare a casa: un ciclo hamiltoniano. Aggiungi qualche arco o togline qualcuno e la domanda diventa sorprendentemente difficile. Se un grafo abbia un ciclo del genere è uno dei problemi più noti a cui nessun computer sa ancora rispondere in fretta per ogni grafo.

Un dodecaedro appiattito con i suoi 20 angoli segnati da consonanti e un ciclo hamiltoniano che li attraversa tutti disegnato con una linea chiara, con un arco rosso tratteggiato dove una ricerca è tornata indietro
Un dodecaedro appiattito con i suoi 20 angoli segnati da consonanti e un ciclo hamiltoniano che li attraversa tutti disegnato con una linea chiara, con un arco rosso tratteggiato dove una ricerca è tornata indietro

Ogni vertice una volta

Un grafo è un insieme di punti, i vertici, uniti da linee, gli archi. Un cammino hamiltoniano segue gli archi e passa per ogni vertice esattamente una volta; un ciclo hamiltoniano torna anche al punto di partenza, quindi ha tanti archi quanti vertici. Un grafo con un ciclo hamiltoniano si dice hamiltoniano. Verificare un percorso proposto è facile: conta i vertici e guarda ogni passo. Trovarne uno, o dimostrare che non ce n'è nessuno, è la parte difficile, perché il numero di ordini in cui i vertici potrebbero essere visitati cresce come n!, già 2,4 × 10¹⁸ per 20 vertici.

Il gioco icosiano di Hamilton

William Rowan Hamilton, il matematico irlandese che scoprì i quaternioni, inventò il gioco icosiano nel 1857. La sua tavola mostrava un dodecaedro appiattito nel piano, con i 20 angoli segnati da consonanti, e il compito principale era mettere pioli numerati da 1 a 20 sugli angoli in modo che numeri consecutivi, e 20 e 1, fossero uniti da archi. Hamilton vendette i diritti per 25 sterline al produttore di giocattoli londinese John Jaques and Son, che lo mise in vendita nel 1859; vendette poco. Il rompicapo ha 30 soluzioni, contando un ciclo una volta qualunque sia la partenza e il verso. La domanda in sé non era nuova: Thomas Kirkman aveva chiesto quali poliedri abbiano un ciclo per tutti i loro angoli in un articolo inviato alla Royal Society nel 1855, e ne aveva mostrato uno che non ne ha.

Giri del cavallo

Un giro del cavallo muove un cavallo degli scacchi in modo che si fermi su ogni casa esattamente una volta: un cammino hamiltoniano nel grafo i cui vertici sono le case e i cui archi sono le mosse del cavallo. Un giro chiuso finisce a una mossa di cavallo dalla partenza, cioè un ciclo hamiltoniano. I giocatori di scacchi ponevano questi problemi più di mille anni fa, ed Eulero li studiò in un articolo del 1759. Nel 1823 H. C. von Warnsdorff propose di andare sempre sulla casa con meno mosse successive; questa regola semplice di solito completa un giro di una scacchiera 8 × 8 senza tornare indietro. Il cavallo cambia sempre colore di casa, quindi un giro chiuso richiede tante case chiare quante scure, il che esclude le scacchiere con un numero dispari di case. Allen Schwenk mostrò nel 1991 esattamente quali scacchiere rettangolari hanno un giro chiuso; tra quelle quadrate, tutte quelle con lato pari da 6 in su. La scacchiera normale ha 13.267.364.410.532 giri chiusi, contati da Brendan McKay nel 1997.

Grafi senza ciclo hamiltoniano

Le dimostrazioni più rapide che non c'è un ciclo sono argomenti di conteggio. Se i vertici si possono colorare con due colori in modo che ogni arco unisca colori diversi, un ciclo alterna e richiede altrettanti vertici per colore; una griglia 5 × 5 ne ha 13 di uno e 12 dell'altro, quindi non ha un ciclo hamiltoniano. Un vertice di taglio, la cui rimozione spezza il grafo, dovrebbe essere attraversato due volte, e un vertice di grado 1 non può esserlo affatto. Alcuni grafi sfuggono a tutti questi argomenti. Il grafo di Petersen, pubblicato da Julius Petersen nel 1898, ha 10 vertici di grado 3 e nessun ciclo hamiltoniano, eppure togliendo un vertice qualsiasi resta un grafo che ne ha uno; è il più piccolo grafo ipohamiltoniano. Il grafo di Herschel, che prende il nome da Alexander Stewart Herschel, il quale scrisse del gioco icosiano nel 1862, ha 11 vertici e 18 archi ed è il grafo di un poliedro con nove facce quadrangolari. Nessun poliedro con meno angoli è privo di ciclo hamiltoniano. Nel 1884 Peter Guthrie Tait congetturò che ogni poliedro con tre spigoli in ogni angolo ne abbia uno; W. T. Tutte trovò un controesempio con 46 vertici nel 1946.

Condizioni che ne garantiscono uno

Se un grafo ha molti archi, un ciclo hamiltoniano è certo. Gabriel Dirac dimostrò nel 1952 che un grafo con n ≥ 3 vertici in cui ogni vertice ha grado almeno n/2 ne ha uno, e Øystein Ore indebolì la condizione nel 1960: basta che due vertici non uniti abbiano sempre gradi con somma almeno n. Entrambe le condizioni valgono in un solo verso. Un semplice anello di 100 vertici ha ovunque grado 2, molto sotto 50, ed è comunque un ciclo hamiltoniano. È questo il quadro generale: ci sono condizioni sufficienti e ci sono ragioni di fallimento, e in mezzo si stende un vasto territorio di grafi che solo una ricerca può decidere.

Perché non si conosce un test veloce

Decidere se un grafo ha un ciclo hamiltoniano è NP-completo; era uno dei 21 problemi della lista di Richard Karp del 1972. Un metodo che lo risolvesse in fretta per ogni grafo risolverebbe in fretta anche migliaia di altri problemi e deciderebbe la questione P contro NP. Il contrasto con i cammini euleriani, che usano ogni arco una volta, è netto: Eulero mostrò nel 1736 che contare i vertici di grado dispari decide quella domanda all'istante. I migliori metodi esatti per i cicli hamiltoniani richiedono ancora tempo esponenziale. La programmazione dinamica su tutti i sottoinsiemi di vertici, trovata da Richard Bellman e da Michael Held e Richard Karp nel 1962, richiede circa n² × 2ⁿ passi, e il metodo randomizzato di Andreas Björklund del 2010 circa 1,657ⁿ. In pratica il backtracking con una buona potatura affronta grafi di qualche decina di vertici, e il problema del commesso viaggiatore, che cerca il ciclo hamiltoniano più corto, è la versione pesata della stessa domanda.

Codici di Gray e l'ipercubo

Scrivi i numeri da 0 a 7 come codici di 3 bit e unisci due codici quando differiscono di esattamente un bit: il risultato è il grafo di un cubo. Un ciclo hamiltoniano che lo percorre, per esempio 000, 001, 011, 010, 110, 111, 101, 100, elenca tutti e otto i codici in modo che ciascuno differisca dal precedente di un solo bit. Un elenco così è un codice di Gray, dal nome di Frank Gray dei Bell Labs, che lo descrisse in un brevetto depositato nel 1947. Ogni ipercubo ne ha uno: scrivi i codici con un bit in meno, poi lo stesso elenco all'indietro, e metti uno 0 davanti alla prima metà e un 1 davanti alla seconda. Gli encoder rotativi usano i codici di Gray perché una lettura presa tra due posizioni non sia mai sbagliata di più di un passo. Il cubo ha 6 cicli hamiltoniani e l'ipercubo di 4 bit ne ha 1.344.

Provalo

Apri l'esploratore di cammini hamiltoniani per provare tu stesso il rompicapo di Hamilton, con anelli tratteggiati che mostrano dove puoi andare, oppure passa a Ricerca e guarda il backtracking al lavoro: il cammino cresce, trattini rossi segnano dove torna indietro, e le barre contano i nodi per ogni lunghezza del cammino. Attiva e disattiva il controllo dei vicoli ciechi, il controllo di connessione e l'ordine di Warnsdorff, confronta quanti nodi richiede ciascuno, conta tutti i cicli di un grafo piccolo, oppure disegna il tuo grafo e vedi quali dei test rapidi si applicano.

Domande frequenti

Un grafo con un circuito euleriano è anche hamiltoniano, o viceversa?

Nessuno dei due segue dall'altro. Il papillon, due triangoli con un vertice in comune, ha un circuito euleriano perché ogni grado è pari, ma nessun ciclo hamiltoniano, poiché il vertice comune dovrebbe essere attraversato due volte. Il grafo completo K₄ ha cicli hamiltoniani, ma tutti e quattro i vertici hanno grado 3, quindi non ha un circuito euleriano.

Un computer non può semplicemente provare tutti gli ordini?

Solo per grafi piccoli. Ci sono n! ordini di n vertici, circa 2,4 × 10¹⁸ per 20. Il backtracking fa molto meglio, perché segue solo gli archi e abbandona un cammino parziale appena si blocca: trova tutti i 30 cicli del dodecaedro a 20 vertici in circa 1.400 passi. Ma per alcuni grafi il numero di cammini parziali cresce comunque in modo esponenziale, e non si conosce alcun metodo che lo eviti per ogni grafo.

Il problema del cammino hamiltoniano è più facile di quello del ciclo?

No, entrambi sono NP-completi. Ciascuno si riconduce all'altro: aggiungi un nuovo vertice unito a tutti i vecchi, e il vecchio grafo ha un cammino hamiltoniano esattamente quando il nuovo ha un ciclo hamiltoniano. Nell'altro verso, un problema di ciclo diventa un problema di cammino aggiungendo una copia di un vertice, con gli stessi vicini, e un nuovo vertice terminale attaccato al vertice e un altro alla sua copia.

Perché un giro del cavallo su una scacchiera 5 × 5 deve iniziare sul colore degli angoli?

Delle 25 case, 13 hanno il colore degli angoli e 12 l'altro, e il cavallo cambia colore a ogni mossa. Un giro di 25 case alterna i colori, quindi inizia e finisce sul colore che ha più case. L'app trova tutti i 1.728 giri aperti della scacchiera 5 × 5, 864 se un giro e il suo inverso contano per uno, e ciascuno inizia e finisce su una casa del colore degli angoli.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri l'esploratore di cammini hamiltoniani