I ponti di Königsberg
Königsberg (oggi Kaliningrad) è un’antica città della Prussia Orientale attraversata dal fiume Pregel.
La “Montagna del re” è stata la città natale del caro vecchio Immanuel Kant ma anche di vecchie volpi matematiche quali David Hilbert, Christian Goldbach e Rudolph Otto Sigismund Lipschitz.
L’aria del mar Baltico sembra proprio fare bene a un certo tipo di pensiero, ma anche la struttura della città sembra voler solleticare la curiosità matematica dei suoi abitanti.
Il fiume Pregel crea nella topografia della città due isole, che sono unite alla terraferma per mezzo di sei ponti, mentre un ponte unisce tra loro le due isole, come illustrato in Figura 1.
Il problema che stuzzica la curiosità degli abitanti di Königsberg durante le passeggiate domenicali riguarda proprio i suoi sette ponti:
è possibile trovare un percorso a piedi per la città in modo tale da attraversare una e una sola volta tutti e sette i ponti?
“Sono il signor Eulero, risolvo problemi”
Al problema dei ponti di Königsberg è possibile rispondere in solo e soltanto due modi: o tale percorso esiste o non esiste.
E in Matematica ogni affermazione deve essere supportata da una dimostrazione.
Nel primo caso bisognerà esibire una soluzione, mentre nel secondo occorrerà mostrare che ogni possibile percorso non fornisce una soluzione adeguata.
La domanda arrivò irrisolta alle orecchie di Leonhard Euler. Il buon Eulero è uno di quei matematici che per rispondere a un problema getta le fondamenta di una nuova branca, bendato e con un braccio legato dietro la schiena.
In questo caso, decide di pubblicare nel 1736 “Solutio problematis ad geometriam situs pertinentis” (“Soluzione a un problema relativo alla geometria di posizione”), ponendo le basi per la moderna Teoria dei Grafi e fornendo una risposta al quesito.
Un grafo è un oggetto costituito da dei puntini (chiamati vertici) collegati tra loro attraverso delle linee (chiamate archi), in modo da ridurre all’osso le proprietà topologiche davvero importanti di un problema.
Nel nostro caso, non abbiamo bisogno di una cartina dell’intera Königsberg, ma solo di quattro vertici che rappresentano le due sponde di terraferma e le due isolette e di sette archi che rappresentano i ponti, come da figura 2.
Forza bruta vs Colpi di fioretto
Una volta ridotto il problema dei ponti di Königsberg al suo scheletro, sono possibili due possibili strategie di risoluzione.
La prima è la forza bruta: dal momento che il numero di possibili combinazioni di percorso è finita, è possibile trovare tutte le possibili passeggiate e verificare se sono soluzioni.
Questo approccio ha il vantaggio di poter essere eseguito da un computer, ma ha lo svantaggio di non farci capire meglio la natura del problema.
Se un domani volessimo risolvere il problema dei ponti di Vladivostok o di Castrovillari dovremmo per forza ricominciare da capo.
L’alternativa è la finezza dei colpi di fioretto dell’intelletto umano.
Si definisce grado di un vertice di un grafo il numero di archi che si connettono a tale vertice.
Nell’esempio di Figura 2, il vertice A è collegato con cinque archi/ponti, quindi è di grado 5, mentre i vertici B, C, e D sono di grado 3.
Arrivato a questo punto il buon Eulero tira fuori dal cilindro il suo Teoremone:
È possibile passare dal vertice X al vertice Y (diverso da X) attraversando una e una sola volta tutti gli archi se e solo se gli unici vertici di grado dispari sono proprio X e Y.
Se X coincide con Y, è possibile passare una e una sola volta tutti gli archi se e solo se tutti i vertici sono di grado pari.
La soluzione del problema dei ponti di Königsberg è allora a portata di mano: ogni vertice del grafo di Figura 2 è di grado dispari, quindi la risposta è no, non esiste un tale percorso.
Con buona pace dei passeggiatori della domenica che con monocoli e ombrellini camminano a braccetto del LungoPregel, sperando di riuscire un giorno a compiere l’impresa per poi vantarsene con gli amici al successivo tè in salotto.
Fonti
[1]- Béla Bollobás, Modern Graph Theory, New York, Springer–Verlag, 1998
[2]- Rudi Mathematici Numero 060 – «Wir müssen wissen, wir werden wissen».
[3]- Tim Räz – Euler’s Königsberg: The Explanatory Power of Mathematics, European Journal for Philosophy of Science volume 8, pages331–346(2018)
[4]-Wikipedia – Problema dei ponti di Königsberg
Matematico, ricercatore e sbadato professionista.
Non chiedetegli di fare i conti al ristorante, non è capace: vi ritroverete a dover pagare quantità immaginarie ed essere costretti a lavare i piatti per qualche settimana.
