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.

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.

Impostazione del problema mediante teoria dei grafi.

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. Nessuno dei grafi completi di ordine pari è invece euleriano.

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

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.

• (EN) Béla Bollobás, Modern Graph Theory, New York, Springer–Verlag, 1998, ISBN 0-387-98488-7.
• Marcel Danesi, Il problema dei ponti di Königsberg di Eulero, in Labirinti, quadrati magici e paradossi logici, Dedalo, Bari 2006, pp. 89-110, su books.google.it.
• (EN) Frank Harary, Graph Theory, Reading (Massachusetts), Addison–Wesley, 1969, ISBN non esistente.

• Multigrafo euleriano
• Multigrafo
• Glossario di teoria dei grafi
• Leonhard Euler

• Wikimedia Commons contiene immagini o altri file sul problema dei ponti di Königsberg

• (EN) Stephan C. Carlson, Königsberg bridge problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Problema dei ponti di Königsberg, su MathWorld, Wolfram Research.
• I ponti di Königsberg su Google Earth.

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