La teoria dei grafi nasce, per tradizione, con un rompicapo. Nella città di Königsberg sette ponti collegavano le due rive del fiume Pregel e due isole. Gli abitanti si chiedevano se fosse possibile fare una passeggiata attraversando ogni ponte esattamente una volta. Nel 1736 Leonhard Euler dimostrò che era impossibile, e il suo ragionamento è ancora oggi il cuore di un'intera famiglia di algoritmi.
Il problema non è solo storico. Chi pianifica i giri degli spazzaneve, della raccolta rifiuti, della lettura dei contatori o dell'ispezione di una rete di tubazioni deve percorrere ogni strada, non visitare ogni punto. È esattamente la domanda di Königsberg.
Cammini e circuiti euleriani
In un grafo, un cammino euleriano percorre ogni arco esattamente una volta. Se termina nel punto di partenza si chiama circuito euleriano.
Euler osservò che ogni volta che si entra in un vertice bisogna anche uscirne, usando due archi diversi. Quindi, in un circuito, ogni vertice deve avere grado pari. Il teorema completo, per grafi non orientati e connessi (ignorando i vertici isolati), dice:
- esiste un circuito euleriano se e solo se tutti i vertici hanno grado pari;
- esiste un cammino euleriano non chiuso se e solo se esattamente due vertici hanno grado dispari; il cammino parte da uno e arriva all'altro;
- in tutti gli altri casi non esiste.
A Königsberg le quattro zone di terra avevano tutte grado dispari: niente passeggiata.
Per i grafi orientati la condizione diventa: in ogni vertice il grado entrante è uguale a quello uscente, e il grafo è connesso considerando gli archi senza verso. Per un cammino non chiuso è ammesso un vertice con un arco uscente in più e uno con un arco entrante in più.
Costruire il circuito: l'algoritmo di Hierholzer
Sapere che il circuito esiste non basta, bisogna costruirlo. L'algoritmo di Hierholzer lo fa in tempo proporzionale al numero di archi.
- Parti da un vertice e cammina usando archi non ancora percorsi, finché non ti blocchi. In un grafo con tutti i gradi pari ti blocchi solo dove sei partito.
- Se restano archi non usati, prendi un vertice del circuito trovato che ne ha ancora, costruisci da lì un nuovo sotto-circuito e inseriscilo in quello principale.
- Ripeti finché tutti gli archi sono stati usati.
Con una pila l'implementazione è compatta:
def hierholzer(adj, start):
# adj: dizionario vertice -> lista di vicini (grafo orientato)
adj = {u: list(vs) for u, vs in adj.items()}
pila, circuito = [start], []
while pila:
u = pila[-1]
if adj.get(u):
pila.append(adj[u].pop())
else:
circuito.append(pila.pop())
return circuito[::-1]
Per un grafo non orientato bisogna anche segnare ogni arco come usato in entrambe le direzioni, di solito con un identificativo per arco.
Un metodo alternativo, l'algoritmo di Fleury, evita di attraversare i ponti finché c'è un'alternativa. È più intuitivo da eseguire a mano, ma molto più lento, perché ogni passo richiede un controllo di connessione.
Il problema del postino cinese
Nella realtà quasi nessuna rete stradale ha tutti i vertici di grado pari. Il postino deve comunque percorrere ogni strada almeno una volta e tornare all'ufficio, e accetta di ripassare su alcune strade. Quali strade ripetere per minimizzare la lunghezza totale? È il problema del postino cinese, così chiamato perché fu studiato dal matematico cinese Kwan Mei-Ko negli anni Sessanta.
Per un grafo non orientato la soluzione è elegante:
- trova i vertici di grado dispari, che sono sempre in numero pari;
- calcola le distanze minime tra tutte le coppie di questi vertici;
- abbinali a due a due in modo da minimizzare la somma delle distanze (un matching perfetto di costo minimo);
- duplica gli archi lungo i cammini minimi scelti: ora tutti i gradi sono pari;
- costruisci il circuito euleriano sul grafo così ottenuto.
La lunghezza ottima è la somma di tutte le strade più la somma delle distanze dell'abbinamento.
Un esempio
Un quartiere ha quattro incroci con grado dispari: A, B, C, D. Le distanze minime sono A–B 2, C–D 3, A–C 4, B–D 5, A–D 6, B–C 4. Gli abbinamenti possibili sono tre:
| Abbinamento | Costo aggiuntivo |
|---|---|
| A–B, C–D | 2 + 3 = 5 |
| A–C, B–D | 4 + 5 = 9 |
| A–D, B–C | 6 + 4 = 10 |
Conviene ripetere le strade sui cammini A–B e C–D: il giro costa 5 unità più della lunghezza totale della rete.
Varianti reali
- Grafo misto: alcune strade sono a senso unico, altre no. Questa versione è molto più difficile e si affronta con euristiche o programmazione intera.
- Postino rurale: solo alcune strade vanno servite, le altre si possono usare per spostarsi. Anche qui il problema diventa difficile in generale.
- Più veicoli e capacità: un camion per la raccolta rifiuti si riempie e deve scaricare. Si parla di problemi di instradamento su archi con capacità, risolti in pratica con metaeuristiche.
In sintesi
- Un cammino euleriano usa ogni arco una volta; il criterio dipende solo dalla parità dei gradi.
- L'algoritmo di Hierholzer costruisce il circuito in tempo lineare nel numero di archi.
- Il postino cinese ripete il minimo di strade necessario a rendere pari tutti i gradi.
- La soluzione combina cammini minimi, matching di costo minimo e circuito euleriano.
- Sensi unici, servizi parziali e capacità rendono il problema reale molto più difficile.
