Verificatore di Cammino Hamiltoniano

Verificatore di Cammino Hamiltoniano

Il Verificatore di Cammino Hamiltoniano stabilisce se un grafo contiene un cammino hamiltoniano — una sequenza che visita ogni vertice esattamente una volta — o un ciclo hamiltoniano, che inoltre ritorna al vertice di partenza. Combina veloci controlli strutturali preliminari (connettività, prerequisiti sui gradi, teorema di Dirac, teorema di Ore) con una ricerca con backtracking ottimizzata dall'euristica di Warnsdorff, e visualizza il percorso trovato con un'animazione passo-passo.

Cos'è un cammino hamiltoniano?

Dato un grafo G = (V, E) con n vertici, un cammino hamiltoniano è una sequenza ordinata v₁, v₂, …, v_n di tutti i vertici tale che ogni coppia consecutiva (v_i, v_i+1) è un arco di G, e ogni vertice appare esattamente una volta. Se inoltre (v_n, v₁) è un arco, la sequenza è un ciclo hamiltoniano.

Il problema deve il suo nome a William Rowan Hamilton, che nel 1857 inventò il gioco icosiano — un rompicapo che chiedeva di trovare un ciclo che visitasse ogni vertice di un dodecaedro regolare esattamente una volta.

Perché è difficile: NP-completezza

Sia il problema di decisione del cammino hamiltoniano che quello del ciclo hamiltoniano sono NP-completi (Karp, 1972). A meno che P = NP, non esiste alcun algoritmo in tempo polinomiale che risolva ogni istanza. Nel peggiore dei casi, il backtracking esplora un albero di ricerca di dimensioni fino a (n−1)! per un ciclo. Questo è il motivo per cui il calcolatore limita l'input a 20 vertici — un piccolo aumento polinomiale di n produce un aumento esplosivo del tempo di esecuzione.

In pratica, l'euristica di Warnsdorff (originariamente ideata da Heinrich Warnsdorff nel 1823 per il problema del giro del cavallo) rende la ricerca drasticamente più veloce su grafi strutturati: ad ogni passo, l'algoritmo estende il cammino corrente verso il vicino non visitato con il minor numero di vicini non visitati rimanenti. Questa regola "greedy" evita che la ricerca finisca in un vicolo cieco e spesso trova un percorso hamiltoniano senza alcun backtracking su grafi regolari.

Condizioni Necessarie — Rifiuto Rapido

Prima di eseguire una ricerca costosa, il calcolatore scarta i grafi che non possono assolutamente contenere un cammino hamiltoniano:

• Connettività. Un cammino hamiltoniano deve visitare ogni vertice, quindi il grafo deve avere esattamente una componente connessa. Per i grafi orientati, è richiesta la connettività debole.
• Grado (non orientato). Al massimo due vertici possono avere grado 1 — questi sono gli unici candidati come estremi del cammino. Per un ciclo hamiltoniano, ogni vertice deve avere un grado almeno pari a 2.
• Grado (orientato). Per un cammino hamiltoniano, al massimo un vertice può avere grado in entrata 0 (l'inizio) e al massimo uno può avere grado in uscita 0 (la fine). Per un ciclo hamiltoniano, ogni vertice deve avere sia grado in entrata ≥ 1 che grado in uscita ≥ 1.

Queste regole scartano molti input impossibili in tempo lineare, evitando sforzi inutili di backtracking.

Condizioni Sufficienti — Teoremi Classici

Diversi teoremi classici forniscono condizioni sufficienti (ma non necessarie) che garantiscono un ciclo hamiltoniano in grafi semplici non orientati. Se una di queste si applica, il calcolatore contrassegna il risultato come "GARANTITO" senza nemmeno eseguire la ricerca (sebbene mostri comunque un ciclo di riscontro).

Teorema di Dirac (1952)

Se G è un grafo semplice non orientato con n ≥ 3 vertici e ogni vertice ha un grado almeno pari a n / 2, allora G possiede un ciclo hamiltoniano.

Teorema di Ore (1960)

Se per ogni coppia di vertici non adiacenti u e v abbiamo deg(u) + deg(v) ≥ n, allora G possiede un ciclo hamiltoniano. La condizione di Ore è strettamente più debole di quella di Dirac, quindi Ore implica Dirac.

Il fallimento della condizione di Dirac o di Ore non significa che il grafo sia privo di un ciclo hamiltoniano — molti grafi non soddisfano nessuna delle due ma ne contengono comunque uno (ad esempio, un semplice n-ciclo ha grado minimo 2, molto al di sotto di n/2 per grandi n).

L'Algoritmo di Ricerca Interno

Quando i controlli preliminari non risolvono la questione, il calcolatore esegue una ricerca con backtracking sulla rappresentazione di adiacenza del grafo. Tattiche chiave:

1. Bitmask del set visitato. I vertici visitati sono memorizzati come una bitmask (test di appartenenza veloce O(1) fino a 20 vertici).
2. Euristica di Warnsdorff. In ogni estensione, i vicini vengono provati in ordine di grado non visitato residuo (il più piccolo per primo).
3. Selezione della radice. Per il ciclo hamiltoniano, è necessario un solo vertice di partenza (i cicli sono invarianti per rotazione). Per il cammino hamiltoniano, le partenze vengono provate in ordine crescente di grado in uscita — le posizioni più rare per prime.
4. Budget di passi. Un limite rigido impedisce alle istanze patologiche di girare all'infinito; l'interfaccia segnala il verdetto come "scaduto" (timed out) se il budget viene esaurito.

Hamiltoniano vs Euleriano

È facile confondere i problemi hamiltoniani ed euleriani — sembrano simili ma sono fondamentalmente diversi:

Formati di Input Supportati

Lista di archi

Un arco per riga, o separati da virgole. Separatori supportati: A-B, A B, A,B, A--B, A->B, A<-B. Usa -> per forzare l'orientamento.

Matrice di adiacenza

Matrice quadrata di valori 0/1, una riga per riga, separati da spazio o virgola. Inserisci le etichette opzionali nel campo Etichette matrice; altrimenti verranno usate automaticamente A, B, C...

Come usare questo verificatore

1. Scegli un formato di input — Lista di archi per piccoli grafi scritti a mano, Matrice di adiacenza per incollare dati da codice o libri di testo.
2. Incolla il tuo grafo nell'area di testo. Per l'input a matrice, fornisci opzionalmente le etichette dei vertici.
3. Scegli cosa verificare: Solo cammino, solo ciclo, o entrambi in una volta.
4. Seleziona il tipo di grafo — Il rilevamento automatico deduce l'orientamento dallo stile delle frecce (->) o dalla simmetria della matrice.
5. Clicca su Verifica Hamiltoniano. La pagina dei risultati mostra il verdetto, il controllo delle condizioni necessarie, i test di Dirac / Ore, il cammino di riscontro (se esistente) e una visualizzazione interattiva.
6. Riproduci il riscontro usando i controlli Play / Step. Osserva il percorso che si illumina arco dopo arco sul grafo.

Esempio Pratico — Il Grafo di Petersen

Il famoso grafo di Petersen (10 vertici, 15 archi, 3-regolare) è un esempio classico di grafo con un cammino hamiltoniano ma nessun ciclo hamiltoniano. Incolla questo nella lista di archi e clicca su Verifica:

Il verificatore conferma: cammino hamiltoniano trovato (es. 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), ma la ricerca esaustiva non trova alcun modo per chiudere il loop — un risultato dimostrato per la prima volta nel 1890.

Applicazioni Comuni

• Logistica e il Problema del Commesso Viaggiatore (TSP) — ogni tour TSP è un ciclo hamiltoniano in un grafo completo pesato.
• Assemblaggio del genoma — la ricostruzione di una sequenza DNA può essere modellata come un cammino hamiltoniano in un grafo di sovrapposizione.
• Progettazione di circuiti — ordinamento dei pin su un PCB per cablaggi di lunghezza minima.
• AI per giochi e puzzle — giri del cavallo sulla scacchiera, gioco icosiano.
• Pianificazione (Scheduling) — sequenziamento di attività in modo che ciascuna possa passare alla successiva in modo fattibile.
• Didattica della combinatoria — illustrare la NP-completezza con piccoli esempi risolvibili a mano.

Domande Frequenti

Cos'è un cammino hamiltoniano?

Un cammino hamiltoniano è un percorso in un grafo che visita ogni vertice esattamente una volta. Prende il nome da William Rowan Hamilton, che studiò il problema sul grafo del dodecaedro nel 1857. Decidere se tale cammino esista è un problema NP-completo, quindi non si conoscono algoritmi in tempo polinomiale validi per tutti i grafi.

In cosa differisce un ciclo hamiltoniano da un cammino hamiltoniano?

Un ciclo hamiltoniano è un cammino hamiltoniano che ritorna al suo vertice di partenza, formando un loop chiuso che visita ogni vertice esattamente una volta. Ogni ciclo hamiltoniano contiene un cammino hamiltoniano (basta togliere l'ultimo arco di chiusura), ma il contrario non è vero: molti grafi hanno un cammino hamiltoniano ma nessun ciclo hamiltoniano.

Cosa dice il teorema di Dirac?

Il teorema di Dirac (1952) afferma che ogni grafo semplice non orientato su n ≥ 3 vertici in cui ogni vertice ha grado almeno n/2 contiene un ciclo hamiltoniano. È una condizione sufficiente ma non necessaria.

Cosa dice il teorema di Ore?

Il teorema di Ore (1960) afferma che se, per ogni coppia di vertici non adiacenti u e v in un grafo semplice su n ≥ 3 vertici, la somma dei loro gradi è almeno n, allora il grafo ha un ciclo hamiltoniano. La condizione di Ore è più debole di quella di Dirac.

Perché la ricerca è limitata a 20 vertici?

I problemi del cammino e del ciclo hamiltoniano sono NP-completi. Il tempo di esecuzione nel caso peggiore cresce esponenzialmente. Con l'euristica di Warnsdorff il calcolatore gestisce velocemente molti grafi fino a 20 vertici, ma istanze più complesse potrebbero andare in timeout.

Cos'è l'euristica di Warnsdorff?

La regola di Warnsdorff, proposta nel 1823 per il problema del cavallo, dice che ad ogni passo dovresti visitare il vertice successivo che ha il minor numero di vicini non visitati rimanenti. Questa regola riduce enormemente l'albero di ricerca e spesso trova soluzioni senza alcun backtracking.

Questo strumento trova tutti i cammini hamiltoniani?

No — trova un singolo cammino o ciclo di riscontro quando ne esiste uno. Contare il numero totale di cammini hamiltoniani è un problema #P-completo, molto più difficile del problema di decisione.

Ulteriori Letture

• Cammino hamiltoniano — Wikipedia
• Problema del cammino hamiltoniano — Wikipedia (EN)
• Teorema di Dirac — Wikipedia (EN)
• Teorema di Ore — Wikipedia (EN)
• Regola di Warnsdorff — Wikipedia

Operazioni matematiche avanzate:

• Calcolatore di Antilogaritmo
• Calcolatore di funzione Beta
• Calcolatore del Coefficiente Binomiale
• Calcolatrice di distribuzione binomiale
• Calcolatore Bitwise
• Calcolatore del Teorema Centrale del Limite
• Calcolatore di combinazione
• Calcolatore di Funzione di Errore Complementare
• Calcolatrice di Numeri Complessi
• Calcolatore di Entropia
• Calcolatore della funzione di errore
• Calcolatore di decadimento esponenziale
• Calcolatore della crescita esponenziale
• Calcolatore dell'Integrale Esponenziale
• calcolatore-di-esponenti-alta-precisione
• Calcolatrice del Fattoriale
• Calcolatore della Funzione Gamma
• Calcolatore del Rapporto Aureo
• Calcolatore del tempo di dimezzamento
• Calcolatore del Tasso di Crescita Percentuale
• Calcolatore di Permutazione
• Calcolatrice della Distribuzione di Poisson
• Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
• Calcolatrice delle probabilità
• Calcolatrice di Distribuzione di Probabilità
• Calcolatore di Proporzioni
• Calcolatore di formula quadratica
• Calcolatrice Scientifica
• Calcolatore di notazioni scientifiche In Primo Piano
• Calcolatore di Cifre Significative Nuovo
• Calcolatore di Somme di Cubi
• Calcolatore di somme di numeri interi positivi
• Calcolatore di Somme di Quadrati
• Generatore di Tabella di Verità
• Calcolatore di Teoria degli Insiemi
• Generatore di Diagramma di Venn (3 Insiemi)
• Calcolatore del Teorema Cinese del Resto
• Calcolatore della Funzione Toziente di Eulero
• Calcolatore dell'Algoritmo Euclideo Esteso
• Calcolatore dell'Inverso Moltiplicativo Modulare
• Calcolatore di Frazioni Continue
• Calcolatore del Percorso più Breve di Dijkstra
• Calcolatore dell'Albero Ricoprente Minimo
• Validatore di Sequenza di Gradi di Grafo
• Calcolatore di Derangement (Sottofattoriale)
• Calcolatore di Numeri di Stirling
• Calcolatore del Principio dei Cassetti
• Calcolatore Distribuzione Stazionaria Catena di Markov
• Calcolatore di Arrotondamento Nuovo
• Calcolatore Distribuzione Binomiale Negativa Nuovo
• Calcolatore Permutazioni con Ripetizione Nuovo
• Calcolatore Esponenziazione Modulare Nuovo
• Calcolatore Radice Primitiva
• Semplificatore di Algebra Booleana Nuovo
• Risolutore di Mappa di Karnaugh (K-Map) Nuovo
• Calcolatore di Colorazione di Grafi Nuovo
• Calcolatore di Ordinamento Topologico Nuovo
• Calcolatore di Matrice di Adiacenza Nuovo
• Calcolatore Inclusione-Esclusione Nuovo
• Risolutore di Programmazione Lineare Nuovo
• Risolutore del Commesso Viaggiatore (TSP) Nuovo
• Verificatore di Cammino Hamiltoniano Nuovo
• Verificatore di Grafo Planare Nuovo
• Calcolatore di Flusso in Rete (Flusso Massimo) Nuovo
• Risolutore del Problema del Matrimonio Stabile Nuovo
• Calcolatore Ordine Teoria dei Gruppi Nuovo
• Calcolatore di Anelli e Campi Nuovo