Problema dei ponti di Königsberg
# Problema dei ponti di Königsberg

Il problema dei sette ponti di Königsberg è un problema ispirato da una città reale e da una situazione concreta. 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.

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. Nel 1736 Eulero affrontò tale problema, dimostrando che la passeggiata ipotizzata non era possibile.

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

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.

## Rappresentazione

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.

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 David 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

Nella storia della matematica il problema dei ponti di Königsberg è uno dei primi problemi della teoria dei grafi discussi 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 XVIII secolo (si veda Storia della combinatoria).

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

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ß, ovvero il castello, del principe Blu, e che sulla riva meridionale sorge quello del principe Rosso; i due principi sono fratelli, ma non sono in buoni rapporti; 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, vi erano riusciti e senza saper ripetere la passeggiata alla luce del giorno.

### L'ottavo ponte del principe Blu

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

Il principe Rosso, adirato 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 da 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

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

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

**L'ottavo ponte del Principe Blu**

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, possiamo immaginare di iniziare la passeggiata dal nodo blu e terminarla nel nodo arancione; per poter garantire la soluzione del problema, bisogna che sugli altri due nodi confluisca un numero pari di spigoli. Aggiungendo un collegamento tra essi, ci troviamo nelle condizioni del teorema di Eulero.

**Il nono ponte del Principe Rosso**

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, si disegna un altro spigolo fra i due.

**Il decimo ponte del Vescovo**

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.

