Problema dei ponti di Königsberg

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Sette ponti di Königsberg)
Vai alla navigazione Vai alla ricerca
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[1]. Nel 1736 Eulero 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 wikitesto]

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 della città di Königsberg e i suoi ponti
Diagramma semplificato dei ponti di Königsberg
Grafo equivalente ai ponti di Königsberg
Impostazione del problema mediante teoria dei grafi.

Rappresentazione[modifica | modifica wikitesto]

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 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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 wikitesto]

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[modifica | modifica wikitesto]

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 wikitesto]

Ottavo, nono e decimo ponte

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.

Il grafo colorato
L'ottavo spigolo

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

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 spigolo
Il decimo spigolo

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

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[modifica | modifica wikitesto]

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 wikitesto]

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

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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