Cammini e circuiti euleriani spiegati

Alcune figure si possono disegnare con un solo tratto, senza staccare la matita e senza ripassare su una linea, e altre no, per quanto si provi. Non serve provare: conta le linee in ogni angolo. Se al massimo due angoli hanno un numero dispari di linee, la figura si può disegnare, e in quegli angoli il tratto deve iniziare e finire. Leonhard Euler trovò questa regola nel 1736, e con essa fondò la teoria dei grafi.

I sette ponti di Königsberg disegnati come grafo: quattro terre come vertici, tutte con un numero dispari di ponti, sulle due sponde di un fiume
I sette ponti di Königsberg disegnati come grafo: quattro terre come vertici, tutte con un numero dispari di ponti, sulle due sponde di un fiume

I sette ponti di Königsberg

La città prussiana di Königsberg, oggi Kaliningrad, sorgeva sulle due rive del fiume Pregel e su due isole, il Kneiphof e la Lomse. Sette ponti univano le quattro parti: due dal Kneiphof a ciascuna riva, uno tra le due isole e uno dalla Lomse a ciascuna riva. Gli abitanti si chiedevano se una passeggiata potesse attraversare ogni ponte esattamente una volta. Euler rispose in un lavoro presentato all'Accademia di San Pietroburgo nel 1735 e stampato nel 1741: non si può. Il passo decisivo fu scartare tutto tranne le parti della città e i ponti tra loro, che è ciò che fa un grafo: un vertice per ogni terra e un arco per ogni ponte, con due archi dove due ponti uniscono le stesse parti.

Ritratto di Leonhard Eulero
Ritratto di Leonhard Eulero
Portrait of Leonhard Euler
Portrait of Leonhard Euler

La regola dei gradi

Il grado di un vertice è il numero di archi che vi arrivano. Un tratto che attraversa un vertice entra da un arco ed esce da un altro, quindi usa gli archi di quel vertice a coppie. Solo il primo e l'ultimo vertice del tratto possono tenere un arco senza compagno. Un vertice di grado dispari deve quindi essere l'inizio o la fine del tratto. Il Kneiphof aveva cinque ponti e le altre tre parti tre ciascuna: quattro vertici dispari, due di troppo. In generale un grafo connesso ha un circuito euleriano, un tratto che finisce dove è iniziato, quando ogni grado è pari, e un cammino euleriano quando esattamente due gradi sono dispari, dall'uno all'altro. Il numero dei vertici dispari non è mai uno, né un altro numero dispari: ogni arco aggiunge 2 alla somma di tutti i gradi, che quindi è pari. Anche questo lo notò Euler, e oggi si chiama lemma delle strette di mano.

Perché la regola basta

Euler mostrò che una figura con più di due vertici dispari non si può tracciare e affermò, senza dimostrarlo, che ogni altra figura connessa si può. La dimostrazione venne da Carl Hierholzer, matematico tedesco morto giovane nel 1871; il suo articolo uscì nel 1873. Parti da un vertice dispari se c'è, altrimenti da dove vuoi, e cammina lungo archi non usati finché puoi. Poiché ogni altro vertice ha grado pari, puoi restare bloccato solo nel vertice finale. Se restano archi, alcuni toccano il percorso fatto, perché la figura è connessa. Da uno di quei vertici cammina di nuovo finché resti bloccato, cosa che ora accade tornando a quel vertice, e inserisci lì l'anello nel percorso. Ripeti finché non resta alcun arco. La dimostrazione è anche l'algoritmo più veloce: ogni arco viene guardato un numero fisso di volte.

L'algoritmo di Fleury: non tagliarti i ponti

Un tratto può fallire anche su una figura che si può disegnare. Prendi due triangoli uniti da un solo arco e parti da un angolo del primo: se passi al secondo triangolo prima di finire il primo, non potrai più tornare. L'arco di collegamento è un ponte: toglierlo divide la figura in due. L'algoritmo di Fleury, del 1883, dà una regola: in ogni vertice prendi un arco che non sia un ponte degli archi rimasti, a meno che non ce ne siano altri. Seguendola si finisce sempre. Verificare un ponte richiede tempo, quindi l'algoritmo di Fleury è più lento di quello di Hierholzer, ma è quello che si può seguire con la matita, e il suggerimento dell'app lo usa.

Sistemare una figura

Una figura con k vertici dispari richiede k/2 tratti. Per disegnarla con uno solo, aggiungi archi che uniscano a coppie i vertici dispari: ogni nuovo arco rende pari due vertici dispari. Con k/2 − 1 archi restano due vertici dispari e si ottiene un cammino; con k/2 non ne resta nessuno e si ottiene un circuito. Un ponte in più a Königsberg, tra due qualsiasi delle quattro parti, avrebbe reso possibile la passeggiata, e due avrebbero permesso un giro completo. La storia ha fatto qualcosa di simile: due ponti andarono perduti nella seconda guerra mondiale e due furono sostituiti da una strada moderna, e i cinque ponti che oggi si trovano nei vecchi punti si possono attraversare una volta ciascuno, da un'isola all'altra.

Contare i modi

La casa di San Nicola, un quadrato con entrambe le diagonali e un tetto, è la versione del rompicapo dei bambini tedeschi: «Das ist das Haus vom Ni-ko-laus» ha otto sillabe, una per ogni linea. I due angoli in basso sono gli unici vertici dispari, e da ciascuno ci sono esattamente 44 modi di disegnarla, 88 in tutto. Per i grafi orientati il numero dei circuiti euleriani ha una formula, il teorema BEST, dai nomi di de Bruijn, van Aardenne-Ehrenfest, Smith e Tutte. Per i grafi ordinari non si conosce una formula simile e il conteggio è ritenuto difficile in generale, quindi l'app conta le figure piccole provando ogni modo e saltando i passi che taglierebbero in due la figura.

Dove si usano i cammini euleriani

Uno spazzaneve, una spazzatrice o un postino vuole percorrere ogni strada una volta e tornare. Se ogni incrocio ha un numero pari di strade, basta un circuito euleriano; altrimenti alcune strade vanno percorse due volte, e scegliere le meno costose è il problema del postino cinese, posto da Meigu Guan nel 1962. Un plotter a penna o un taglio laser risparmia tempo tracciando più linee possibile senza sollevare l'utensile. Nel sequenziamento del genoma milioni di brevi frammenti di DNA vengono assemblati cercando un cammino euleriano in un grafo di de Bruijn, in cui ogni frammento è un arco. E la stessa regola dice quali disegni di un libro di enigmi vale la pena di tentare.

Prova tu

Apri il cerca cammini euleriani per tracciare dodici figure, da Königsberg nel 1736 e oggi fino a stelle, quadrati annidati e un cubo, oppure disegna le tue con archi paralleli. I vertici dispari sono pieni, ogni vertice mostra il suo grado e la regola dei gradi sotto la figura dice che cosa è possibile e quali archi la sistemerebbero. Se resti bloccato, l'app dice se sei partito dal vertice sbagliato o hai attraversato un ponte troppo presto, e a quale passo. Suggerimento dà un arco sicuro e Risolvi disegna la figura con l'algoritmo di Fleury, mostrando la verifica del ponte, o con quello di Hierholzer, mostrando ogni inserimento.

Domande frequenti

Un cammino euleriano è la stessa cosa di un cammino hamiltoniano?

No. Un cammino euleriano usa ogni arco una volta e può passare più volte da un vertice; un cammino hamiltoniano visita ogni vertice una volta e non deve usare ogni arco. Contare i vertici dispari dice subito se un grafo ha un cammino euleriano, ma per i cammini hamiltoniani non si conosce alcun test rapido, e trovarne uno è uno dei classici problemi difficili dell'informatica.

La regola dei gradi vale quando due vertici sono uniti da più archi?

Sì. Ogni arco conta nel grado di entrambi i suoi estremi, che un altro arco unisca o no gli stessi due vertici. Königsberg è un multigrafo di questo tipo, con due ponti dal Kneiphof a ciascuna riva. Un arco da un vertice a sé stesso, un cappio, aggiunge 2 al suo grado e non cambia mai la sua parità.

E con i sensi unici?

In un grafo orientato ogni arco ha un verso, e la regola confronta gli archi che entrano in ogni vertice con quelli che ne escono. C'è un circuito euleriano quando in ogni vertice entrano tanti archi quanti ne escono e gli archi stanno insieme, e un cammino euleriano quando un vertice ha un arco uscente in più, un altro un arco entrante in più e tutti gli altri sono bilanciati. Il cammino va allora dal primo al secondo.

Può esistere una figura con esattamente un vertice dispari?

No. I gradi di tutti i vertici sommati danno il doppio del numero degli archi, perché ogni arco ha due estremi. La somma è pari, quindi anche il numero dei gradi dispari in essa deve essere pari: 0, 2, 4 e così via, mai 1 o 3.

Pronto a provarlo?

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

Apri il cerca cammini euleriani