I sette ponti di Königsberg: il gioco che fondò la teoria dei grafi

Esistono problemi che sembrano giochi da bambini e che invece fondano interi rami della matematica. Il più celebre è quello dei sette ponti di Königsberg: una passeggiata apparentemente innocua che, nel 1736, spinse Leonhard Euler a inventare un modo nuovo di guardare il mondo. Da quella riflessione nacquero la teoria dei grafi e i primi passi della topologia, le discipline che oggi fanno funzionare il navigatore satellitare, internet e le reti elettriche.

Una città, un fiume, sette ponti

Königsberg era la capitale della Prussia orientale (oggi è Kaliningrad, in Russia). Il fiume Pregel l'attraversava dividendola in quattro porzioni: le due rive e due isole, collegate fra loro da sette ponti. Tra gli abitanti circolava un passatempo: era possibile fare una passeggiata che attraversasse tutti e sette i ponti una sola volta, senza mai ripassare su nessuno? Tutti ci provavano, nessuno ci riusciva, ma nessuno sapeva dire se il fallimento dipendesse dalla sfortuna o da un'impossibilità di principio.

L'intuizione di Euler: dimenticare la geometria

Quando il problema arrivò sul tavolo di Leonhard Euler, allora all'Accademia delle Scienze di San Pietroburgo, il matematico svizzero ebbe l'idea che avrebbe cambiato tutto. Capì che la soluzione non dipendeva né dalle distanze, né dalle forme, né dalla lunghezza dei ponti: contava soltanto come le diverse porzioni di terra erano connesse tra loro. Euler ridusse quindi la mappa a uno schema astratto: ogni lembo di terra diventava un punto (un "nodo"), ogni ponte una linea (un "arco") che univa due punti. La città di pietra svaniva, restava solo la sua struttura di collegamenti.

Fu un gesto rivoluzionario. Per la prima volta un problema veniva risolto guardando non alle misure, ma alle relazioni: quella che Gottfried Leibniz aveva chiamato geometria situs, la geometria della posizione. Come ricostruisce la voce dell'Encyclopædia Britannica dedicata al problema dei ponti, Euler dimostrò che la questione poteva essere risolta in modo puramente logico, senza bisogno di provare tutti i percorsi a tentativi.

La regola dei nodi dispari

Ecco il ragionamento, sorprendentemente semplice. Pensiamo a un lembo di terra che non sia né l'inizio né la fine della passeggiata: ogni volta che ci entriamo attraverso un ponte, dobbiamo uscirne attraverso un altro. I ponti che vi arrivano devono quindi potersi accoppiare a due a due, cioè essere in numero pari. Solo i punti di partenza e di arrivo possono permettersi un numero dispari di ponti.

Euler tradusse tutto questo in un principio generale, oggi alla base della teoria dei grafi: un percorso che attraversa ogni arco esattamente una volta può esistere soltanto se i nodi con un numero dispari di collegamenti sono al massimo due. A Königsberg, però, tutti e quattro i lembi di terra avevano un numero dispari di ponti. Quattro nodi dispari significavano una sola, inappellabile conclusione: la passeggiata era impossibile. Non per mancanza di abilità, ma per le leggi della matematica. Il lavoro venne presentato nel 1736 e pubblicato con il titolo Solutio problematis ad geometriam situs pertinentis; oggi la biografia di Euler curata dall'archivio MacTutor dell'Università di St Andrews lo cita come uno dei suoi contributi più influenti.

Dalla passeggiata alle reti del mondo

Quello che sembrava un rompicapo da osteria era in realtà l'atto di nascita di una nuova matematica. Riducendo oggetti reali a nodi e archi, Euler aveva inventato il grafo, lo strumento con cui oggi descriviamo qualsiasi rete: le strade percorse dal navigatore, i cavi che trasportano l'elettricità, i collegamenti tra i computer di internet, le amicizie sui social network, perfino le interazioni tra le proteine in una cellula. Ogni volta che un algoritmo calcola il percorso più breve tra due punti, sta camminando sulle orme di quella passeggiata mancata.

Il problema dei ponti è anche considerato un antenato della topologia, la branca che studia le proprietà delle figure che non cambiano quando le si deforma senza strapparle: ciò che conta è la connessione, non la misura. Lo stesso Euler avrebbe poi formulato la celebre relazione tra vertici, spigoli e facce dei poliedri, un altro pilastro di questa disciplina.

Epilogo: e oggi?

La storia ha un finale curioso. La Königsberg di Euler non esiste più: pesantemente bombardata durante la Seconda guerra mondiale e poi ricostruita come città sovietica, ha perso alcuni dei suoi ponti storici. Con un numero diverso di collegamenti, la geometria del problema è cambiata, e in determinate configurazioni una passeggiata euleriana sarebbe oggi possibile. Ma la lezione che la città ha lasciato all'umanità non dipende più dai suoi ponti: ci ha insegnato che, a volte, per risolvere un problema basta smettere di guardarne i dettagli e cominciare a vederne la struttura.

Dal salto di Eulero agli algoritmi di oggi

La distinzione introdotta da Eulero — tra un percorso che attraversa ogni arco una sola volta (cammino euleriano) e uno che torna anche al punto di partenza (circuito euleriano) — non è un'astrazione fine a sé stessa. È esattamente il tipo di problema che si pone chi deve progettare il giro di uno spazzaneve, la raccolta dei rifiuti o la lettura dei contatori: passare per ogni strada una volta sola, sprecando meno carburante possibile. Gli informatici lo chiamano "problema del postino cinese", ed è un discendente diretto della passeggiata di Königsberg.

Da quel primo grafo sono nati strumenti che usiamo ogni giorno senza accorgercene: gli algoritmi che calcolano il percorso più breve sulle mappe, quelli che instradano i pacchetti di dati su internet, perfino i modelli con cui si studia la diffusione di un'epidemia. Tutto, in fondo, comincia da quattro lembi di terra e sette ponti.