Nel Settecento la città di Königsberg era attraversata dal fiume Pregel. Due grandi isole e le rive erano collegate da sette ponti.
Tra gli abitanti circolava una domanda semplice da formulare e sorprendentemente difficile da risolvere: è possibile fare una passeggiata attraversando ciascuno dei sette ponti una sola volta?
Non c’è libro sulla teoria dei grafi che non citi questo “enigma”.
PROBLEMA 1729 #014
Tempo: 10-15 minuti
Difficoltà:
⭐⭐⭐
Classificazione: 3 su 5.
Categoria: Grafi e ragionamento logico
Il problema
Immagina quattro zone di terra separate dal fiume e collegate da sette ponti.
Vuoi fare una passeggiata attraversando ogni ponte una sola volta.
Puoi partire da qualunque punto e terminare dove vuoi.
Non puoi attraversare un ponte due volte e non puoi saltarne nessuno.
È possibile?
Prima di continuare, prova a disegnare quattro zone e sette collegamenti. Cerca un percorso. Se fallisci, chiediti se dipende dal tentativo scelto oppure dalla struttura stessa del problema.
💡 Mostra un indizio
Non concentrarti sulla forma della città o sulla lunghezza dei ponti.
Conta invece quanti ponti arrivano in ciascuna delle quattro zone.
💡 Mostra un altro indizio
Ogni volta che entri in una zona passando su un ponte, per continuare la passeggiata devi normalmente uscirne attraverso un altro ponte.
I ponti tendono quindi a essere usati a coppie: uno per entrare e uno per uscire.
Le sole eccezioni possono essere il punto di partenza e il punto di arrivo.
✅ Mostra la soluzione
No. La passeggiata è impossibile.
Il motivo non dipende da quanto siamo bravi a cercare un percorso.
Rappresentiamo ogni zona di terra con un punto e ogni ponte con una linea che collega due punti.
Le quattro zone hanno rispettivamente 3, 3, 3 e 5 ponti incidenti.
Tutte e quattro hanno quindi un numero dispari di ponti.
In una passeggiata che attraversa ogni ponte una sola volta, ogni zona intermedia deve essere raggiunta e poi abbandonata: i ponti utilizzati lì si accoppiano quindi a due a due.
Solo il punto di partenza e quello di arrivo possono avere un numero dispari di passaggi.
Perciò un percorso di questo tipo può esistere soltanto se i vertici con numero dispari di collegamenti sono zero oppure due.
A Königsberg sono invece quattro.
Di conseguenza attraversare tutti e sette i ponti una sola volta è matematicamente impossibile.
La matematica dentro al gioco
La grande intuizione di Leonhard Euler fu eliminare dal problema tutto ciò che non era essenziale.
Non servono la forma delle isole, le distanze, le curve del fiume o la posizione precisa dei ponti.
Conta soltanto quali zone sono collegate fra loro.
Nasce così una rappresentazione astratta:
le zone di terra diventano vertici;
i ponti diventano archi.
Il numero di archi che arrivano a un vertice si chiama grado del vertice.
Un percorso che usa ogni arco esattamente una volta viene oggi chiamato cammino euleriano.
Per un grafo connesso, un cammino euleriano aperto esiste se e solo se ci sono esattamente due vertici di grado dispari. Se tutti i vertici hanno grado pari, esiste invece un percorso chiuso che ritorna al punto di partenza.
Il problema dei ponti è quindi un ottimo esempio di un’idea fondamentale della matematica: trasformare un problema concreto nella sua struttura essenziale.
Una variante per te
Immagina di poter costruire un solo nuovo ponte a Königsberg.
Puoi scegliere liberamente quali due zone collegare.
È possibile aggiungere un ponte in modo da rendere possibile una passeggiata che attraversi ogni ponte esattamente una volta?
Prova a ragionare non disegnando molti percorsi, ma osservando come cambia la parità del grado dei due vertici collegati dal nuovo ponte.
Suggerimento: aggiungendo un arco, il grado di due vertici cambia di uno.
Lo sapevi?
Nel 1736 Leonhard Euler affrontò il problema in un lavoro dal titolo Solutio problematis ad geometriam situs pertinentis.
Il passaggio decisivo fu proprio quello di ignorare la geometria tradizionale e considerare soltanto le connessioni tra le diverse parti della città.
Per questo motivo il problema dei ponti di Königsberg viene spesso indicato come uno dei punti di partenza della teoria dei grafi e, più in generale, della matematica delle reti.
Oggi idee dello stesso tipo compaiono nello studio di reti informatiche, trasporti, circuiti, mappe, social network e moltissimi problemi algoritmici.
Problema 1729
#014 — I ponti di Königsberg
Giochi, enigmi e idee matematiche per menti curiose.
[…] lo stesso salto concettuale che incontriamo nel problema dei ponti di Königsberg: si cancellano distanze, forme e paesaggi e si conserva soltanto la rete delle relazioni. Una carta […]
[…] esempio si percorrono in una sola direzione. È lo stesso linguaggio dei grafi incontrato nei ponti di Königsberg: i luoghi diventano nodi, i collegamenti diventano […]
Lascia un commento