Problema dei ponti di Königsberg

Da Wikipedia, l'enciclopedia libera.
Mappa di Königsberg ai tempi di Eulero che mostra l'effettiva impostazione della città, evidenziando il fiume Pregel e i suoi ponti

Il problema dei sette ponti di Königsberg è un problema ispirato da una città reale e da una situazione concreta[1]. Königsberg, un tempo in Prussia Orientale e oggi exclave russa sul Baltico nota con il nome di Kaliningrad, è percorsa dal fiume Pregel e da suoi affluenti e presenta due estese isole che sono connesse tra di loro e con le due aree principali della città da sette ponti[1]. Nel corso dei secoli è stata più volte proposta la questione se sia possibile con una passeggiata seguire un percorso che attraversi ogni ponte una e una volta soltanto e tornare al punto di partenza[1]. Nel 1736 Leonhard Euler affrontò tale problema, dimostrando che la passeggiata ipotizzata non era possibile[1].

Non sembra avere un fondamento storico, ma piuttosto essere una leggenda urbana, l'affermazione secondo la quale intorno al 1750 i cittadini benestanti di Königsberg la domenica passeggiassero per la loro città cercando invano di risolvere il problema.

Impostazione e soluzione di Eulero[modifica | modifica sorgente]

Eulero ha il merito di aver formulato il problema in termini di teoria dei grafi, astraendo dalla situazione specifica di Königsberg; innanzitutto eliminò tutti gli aspetti contingenti ad esclusione delle aree urbane delimitate dai bracci fluviali e dai ponti che le collegano; secondariamente rimpiazzò ogni area urbana con un punto, ora chiamato vertice o nodo e ogni ponte con un segmento di linea, chiamato spigolo, arco o collegamento.

Konigsberg bridges.png7 bridges.svgGrafo ABCD.jpg

Rappresentazione[modifica | modifica sorgente]

Eulero rappresentò la disposizione dei sette ponti congiungendo con altrettante linee le quattro grandi zone della città, come nella prima immagine. Si noti che dai nodi A, B e D partono (e arrivano) tre ponti; dal nodo C, invece, cinque ponti. Questi sono i gradi dei nodi: rispettivamente, 3, 3, 5, 3.
Prima di raggiungere una conclusione, Eulero ha ipotizzato delle situazioni diverse di zone e ponti (nodi e collegamenti): con quattro nodi e quattro ponti è possibile partire, ad esempio, da A, e tornarci passando per tutti i ponti una e una sola volta. Il grado di ciascun nodo è un numero pari. Se invece si parte da A per arrivare a D, ogni nodo è di grado pari a eccezione di due nodi, di grado dispari (uno). Sulla base di queste osservazioni, Eulero ha enunciato il seguente teorema:

Un qualsiasi grafo è percorribile se e solo se ha tutti i nodi di grado pari, o due di essi sono di grado dispari; per percorrere un grafo "possibile" con due nodi di grado dispari, è necessario partire da uno di essi, e si terminerà sull’altro nodo dispari.
Eulero a 49 anni, dipinto da Emanuel Handmann (1756)

Pertanto è impossibile percorrere Königsberg come richiesto dalla tesi, poiché tutti i nodi sono di grado dispari.

Va osservato che la teoria dei grafi ha strette connessioni con la topologia: la forma di un grafo, o meglio di una raffigurazione di un grafo o di una sua variante (v. grafo arricchito) può essere modificata spostando i vertici e distorcendo le linee che li collegano, pur di mantenere i collegamenti effettivi. Non conta se un collegamento si presenta rettilineo o curvato e neppure se un vertice sta da una parte o dall'altra rispetto a un collegamento di vertici vicini.

Eulero ha dimostrato che per un grafo qualsiasi un cammino con le caratteristiche desiderate è possibile se e solo se il grafo non ha vertici (i punti nella raffigurazione del grafo) che sono raggiunti da un numero dispari di spigoli. Un tale cammino è chiamato circuito euleriano. Dato che il grafo relativo a Königsberg ha quattro di tali vertici, il cammino non esiste.

Se si lascia cadere la richiesta che il punto di inizio e il punto finale coincidano, allora vi possono essere nessuno o due vertici toccati da un numero dispari di spigoli. Un tale cammino viene chiamato cammino euleriano.

Tra i grafi euleriani ricordiamo tutti grafi completi di ordine dispari, la stella di Davide e le scimitarre di Allah. Nessuno dei grafi completi di ordine pari è invece euleriano.

Per un esame solo matematico del problema v. multigrafo euleriano.

Importanza nella storia della matematica[modifica | modifica sorgente]

Nella storia della matematica il problema dei ponti di Königsberg è uno dei primi problemi della teoria dei grafi discusso formalmente; esso si può anche considerare uno dei primi problemi concernenti la topologia. Non si può invece considerare uno dei primi problemi della combinatoria, altra area della matematica alla quale la teoria dei grafi viene fatta afferire, in quanto i primi problemi combinatorici sono stati affrontati vari secoli prima del diciottesimo (v. Storia della combinatorica).

Il confronto fra una mappa anche schematica di Königsberg e la raffigurazione del grafo che schematizza il problema costituisce una buona indicazione dell'idea che la topologia prescinda dalla forma rigida degli oggetti che studia.

Variazioni[modifica | modifica sorgente]

L'enunciato originale del problema concerne vertici non identificati, cioè caratterizzati solo dai loro collegamenti. Vi sono invece variazioni su questo tema che possono essere utili per introdurre il problema nell'insegnamento e che si preoccupano di identificare i vertici del grafo con personaggi e ruoli.

Si precisa quindi che sulla riva settentrionale della città sorge lo Schloß, il castello per chi non conoscesse ancora la parola tedesca, del principe Blu e che sulla riva meridionale sorge quello del principe Rosso; i due principi sono fratelli, ma è un caso dei fratelli-coltelli; sull'isola orientale vi è la Kirche, la chiesa, sede del Vescovo; infine nell'isola centrale si trova una Gasthaus, un'osteria. Come si vedrà poi le relazioni fra i notabili della città, tra i quali va realisticamente considerato anche l'oste, non sono sempre facili.

Seguendo con attenzione l'ordine cronologico dei fatti, bisogna ricordare che molti abitanti della città avevano l'abitudine la sera di trattenersi alquanto alla Gasthaus e quindi di tentare l'impresa chiamata passare i ponti; alcuni poi tornavano a festeggiare la loro riuscita con ulteriori libagioni, ma senza riuscire a spiegare in modo soddisfacente come a loro dire erano riusciti e senza saper ripetere la passeggiata alla luce del giorno.

L'ottavo ponte del principe Blu[modifica | modifica sorgente]

Il principe Blu, dopo aver analizzato il sistema dei ponti cittadini con l'aiuto della teoria dei grafi, si convince dell'impossibilità di passare i ponti. Decide allora di costruire di nascosto un ottavo ponte che gli permetta la sera di passare i ponti partendo dal suo Schloß e finendo alla Gasthaus dove potersi vantare della sua riuscita; e inoltre fa in modo che il principe Rosso non riesca a fare altrettanto a partire dal suo Schloß.

  • Dove costruisce l'ottavo ponte il principe Blu?

Il nono ponte del principe Rosso[modifica | modifica sorgente]

Il principe Rosso, imbufalito per la mossa del fratello, capisce che può reagire solo dopo aver studiato la teoria dei grafi; dopo un attento studio anche lui decide di costruire di nascosto un altro ponte che consenta a lui di traversare i ponti in modo di raggiungere dal suo Schloß la Gasthaus e qui prendere per i fondelli il fratello al quale diventa impossibile passare i ponti alla sua maniera.

  • Dove costruisce il nono ponte il principe Rosso?

Il decimo ponte del Vescovo[modifica | modifica sorgente]

Il Vescovo ha dovuto assistere alla dispendiosa contesa cittadina con crescente irritazione. Essa ha portato alla formazione di due facinorose fazioni e ha fatto crescere il numero degli eccessivi frequentatori della Gasthaus, con danno della quiete pubblica. Quindi anche lui, dopo un accurato studio della teoria dei grafi, decide di costruire un decimo ponte che consenta a tutti i cittadini di passare tutti i ponti e fare ritorno alla propria casa tra i tranquilli affetti familiari.

  • Dove costruisce il decimo ponte il Vescovo?

Soluzioni[modifica | modifica sorgente]

Ottavo, nono e decimo ponte

Riduci la città, come sopra, a un grafo. Colora ciascun nodo come nel problema classico, nessuna passeggiata di Eulero è possibile. Tutti i quattro nodi hanno un numero dispari di spigoli.

Il grafo colorato
L'ottavo spigolo

L'ottavo ponte del Principe Blu[modifica | modifica sorgente]

Le passeggiate di Eulero sono possibili se esattamente 2 nodi posseggono un numero dispari di spigoli, che sono esattamente i nodi iniziale e finale della passeggiata. Poiché il problema presenta solo 4 nodi, tutti con grado dispari, la passeggiata inizia nel nodo blu e termina nel nodo arancione. Bisogna quindi disegnare un nuovo spigolo fra gli altri due nodi. Poiché hanno formalmente un numero dispari di spigoli, bisogna creare un numero pari di spigoli in tutti i nodi che non siano quello iniziale e finale. Un cambiamento nella parità da grado dispari a grado pari. Sarebbe altrimenti bastato erigere un ponte che partisse dal bianco all'arancione. In questo modo solo due punti avevano un numero dispari di ponti.

Il nono spigolo
Il decimo spigolo

Il nono ponte del Principe Rosso[modifica | modifica sorgente]

Risolto il problema dell'ottavo ponte, il nono ponte presenta una soluzione facile. Si richiede di utilizzare il nodo rosso come punto di partenza e l'arancione come arrivo. Per cambiare la parità dei nodi rosso e blu, disegna un altro spigolo fra i due.

Il decimo ponte del Vescovo[modifica | modifica sorgente]

Il decimo ponte va in una direzione leggermente diversa. Il Vescovo vuole che ogni cittadino ritorni al punto di partenza. Questo è un cammino euleriano e richiede che tutti i nodi siano di grado pari. Dopo la soluzione del nono ponte i nodi rosso e arancione sono di grado dispari quindi devono essere cambiati aggiungendo un nuovo spigolo fra di loro.

Note[modifica | modifica sorgente]

  1. ^ a b c d Harary, op. cit., pp. 1-2.

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica