Primi elementi della teoria dei grafi

Circuito hamiltoniano

Il matematico irlandese William Hamilton (1805-1865) nel 1859 propose il gioco del dodecaedro: su ognuno dei 20 vertici di un dodecaedro regolare di legno mise il nome di una città famosa e chiese: è possibile per un viaggiatore partire da una città visitare una e una sola volta tutte le altre città, trasferendosi lungo gli spigoli del solido, e ritornare alla città di partenza?

In seguito Hamilton propose una versione bidimensionale del gioco dove il dodecaedro era sostituito da un grafo equivalente, dal punto di vista topologico, al dodecaedro e chiedeva se esistesse un percorso chiuso che attraversasse tutti i vertici una sola volta.

Ecco una possibile soluzione del gioco sia sul solido che sul grafo bidimensionale.

Un percorso chiuso che passa una volta sola per ogni vertice di un grafo è detto circuito hamiltoniano e un grafo che contenga un circuito hamiltoniano è detto grafo hamiltoniano.

Un circuito euleriano e un circuito hamiltoniano sono duali perchè nel primo si chiede di percorrere ogni spigolo una sola volta tornando nel vertice iniziale, nel secondo si chiede di passare per ogni vertice una sola volta tornando nel vertice iniziale. La soluzione ai due quesiti è però molto diversa perchè possiamo stabilire facilmente se un grafo è euleriano o no, invece non siamo in grado di stabilire in modo semplice se un grafo è hamiltoniano o no. L'esistenza di un circuito hamiltoniano deve essere valutata caso per caso e non esiste una qualche relazione tra un grafo euleriano e un grafo hamiltoniano. Un grafo può non essere sia euleriano che hamiltoniano, oppure può essere euleriano ma non hamiltoniano e vicevera, oppure può essere sia euleriano che hamiltoniano. Ad esempio, un grafo non connesso non è nè euleriano nè hamiltoniano, invece il grafo:

è euleriano ma non hamiltoniano. il grafo:

è hamiltoniano ma non euleriano. Il grafo:

è sia euleriano che hamiltoniano.

I circuiti hamiltoniani sono fondamentali in molti problemi di ottimizzazione e analisi delle reti e sono utili per progettare percorsi efficienti in robotica e automazione.