I sette ponti di Königsberg

Per molto tempo gli abitanti di Königsberg, nel XVIII secolo, si sono scervellati su un indovinello: la città è attraversata dal fiume Pregel, che forma due isole. Sul fiume ci sono in tutto sette ponti che portano alle isole. Durante una passeggiata domenicale è possibile attraversare tutti i ponti, ma ciascuno esattamente una volta? Vediamo come erano disposti i ponti sul fiume:

È possibile iniziare la nostra passeggiata da un punto e attraversare tutti i ponti esattamente una volta? Possiamo provare: partiamo in basso a sinistra, saliamo e poi proseguiamo via via verso destra, così:

Vediamo che abbiamo attraversato sei ponti su sette, uno ci è sfuggito. Possiamo provare un altro percorso…

Anche questa volta abbiamo attraversato solo sei dei sette ponti della nostra Königsberg. Sembra quasi che con una sola passeggiata non si possa attraversare ogni ponte esattamente una volta. Un giorno si imbatté in questo problema un famoso matematico, Leonhard Euler, in italiano Eulero. Che famoso – Eulero è stato una vera leggenda della matematica, e da lui prende il nome perfino il numero di Eulero (che da noi si chiama più spesso numero di Nepero). Eulero si disse che avrebbe risolto l’enigma. Cominciò contrassegnando le singole isole, o parti della città, da cui e verso cui partivano i ponti:

Eulero fece ora il seguente ragionamento: se a un’isola portano un numero pari di ponti, possiamo attraversare tutti questi ponti durante una passeggiata, qualunque sia il punto da cui partiamo. Insomma, con un ponte arriviamo sull’isola, con un altro ce ne andiamo – il numero di ponti ancora da attraversare diminuisce di due. Per poter arrivare sull’isola con un ponte e andarcene con un altro servono due ponti. Se all’isola portano sei ponti, visiteremo l’isola tre volte. Per esempio, immaginiamo che all’isola B portassero quattro ponti, così:

Allora con una sola passeggiata domenicale possiamo attraversare tutti i ponti, da qualunque punto partiamo. Provaci! Nella figura ho evidenziato un percorso. Immaginiamo ora che all’isola B portasse anche un ponte dall’isola D:

Vediamo che il percorso che abbiamo scelto non ci permette di attraversare tutti i ponti esattamente una volta. Dovremmo tornare sull’isola B con uno dei ponti e poi passare sull’isola D. Ma possiamo scegliere un altro percorso. Possiamo iniziare la passeggiata dall’isola B e poi riusciamo ad attraversare tutti i ponti esattamente una volta:

Abbiamo iniziato la passeggiata dall’isola B, siamo andati su fino alla zona A, poi con un ponte di nuovo su B, alla zona C, poi di nuovo sull’isola B e infine sull’isola D. Se quindi partiamo da un’isola con un numero dispari di ponti, riusciamo ad attraversare tutti i suoi ponti esattamente una volta. Oppure possiamo fare il contrario: possiamo iniziare dall’isola D e finire sull’isola B.

Eulero notò quindi che, perché si possano attraversare tutti i ponti esattamente una volta, serve che tutte le isole abbiano un numero pari di ponti, oppure ci possono essere due isole con un numero dispari di ponti – su un’isola con un numero dispari di ponti iniziamo e sull’altra finiamo. Tutte le altre isole devono avere un numero pari di ponti. Se guardiamo i sette ponti originali di Königsberg:

vediamo che ogni isola ha un numero dispari di ponti! L’isola A ne ha 3, B ne ha 5, C ne ha 3 e anche D ne ha 3. Per questo l’indovinello non ha soluzione – non è possibile attraversare tutti e sette i ponti esattamente una volta in una sola passeggiata domenicale. Se demolissimo uno qualsiasi dei ponti, l’indovinello avrebbe di colpo una soluzione. Demoliamo, per esempio, uno dei ponti tra le isole B e C:

Vediamo che improvvisamente l’isola B ha 4 ponti e l’isola C due ponti. Per le isole A e D il numero di ponti non è cambiato. Abbiamo all’improvviso due isole con un numero pari di ponti e due isole con un numero dispari di ponti. Se iniziamo la passeggiata da una delle isole con un numero dispari di ponti, riusciamo ad attraversare tutti i ponti esattamente una volta. Nella figura siamo partiti dall’isola A e abbiamo finito sull’isola D.

Eulero ha così risolto un altro famoso problema matematico e, più o meno, ha posto le basi di quella che oggi chiamiamo teoria dei grafi; in suo onore un grafo in cui si possono percorrere tutti gli archi esattamente una volta si chiama, nel linguaggio della teoria dei grafi, grafo euleriano.