Sette ponti di Königsberg

Analisi di Eulero

In primo luogo, Euler ha sottolineato che la scelta del percorso all'interno di ogni massa terrestre non ha importanza. L'unica proprietà importante di un percorso è l'ordine in cui i ponti sono attraversati. Quindi, ha cambiato il problema in termini astratti. Questo gettò le basi della teoria dei grafi. Ha rimosso tutte le caratteristiche tranne l'elenco delle masse terrestri e i ponti che le collegano. Nel linguaggio della teoria dei grafi, sostituì ogni massa di terra con un "vertice" o nodo astratto. Poi sostituì ogni ponte con una connessione astratta, un "bordo". Un bordo (strada) registrava quali due vertici (masse terrestri) erano collegati. In questo modo, formò un grafo.

→ →

Il grafico disegnato è un'immagine astratta del problema. Quindi, i bordi possono essere uniti in qualsiasi modo. È importante solo se due punti sono collegati o meno. Cambiare l'immagine del grafico non cambia il grafico stesso.

In seguito, Eulero osservò che (tranne che nei punti finali del cammino), ogni volta che si entra in un vertice con un ponte, si lascia il vertice con un ponte. In qualsiasi cammino del grafico, il numero di volte che si entra in un vertice è uguale al numero di volte che lo si lascia. Se ogni ponte è stato attraversato esattamente una volta, ne consegue che, per ogni massa di terra (eccetto quelli scelti per la partenza e l'arrivo), il numero di ponti che toccano quella massa di terra deve essere pari. Questo perché se ci sono n ponti, essa viene attraversata esattamente 2n volte. Tuttavia, tutte e quattro le masse terrestri nel problema originale sono toccate da un numero dispari di ponti (una è toccata da 5 ponti, e ciascuna delle altre tre è toccata da 3). Ci sono al massimo due masse che possono essere i punti finali di una passeggiata. Quindi la proposizione di una passeggiata che attraversa ogni ponte una volta sola porta a una contraddizione.

Nel linguaggio moderno, Eulero mostra che se una passeggiata attraverso un grafico che attraversa ogni bordo una volta è possibile o meno dipende dai gradi dei nodi. Il grado di un nodo è il numero di bordi che lo toccano. Euler mostra che una condizione necessaria per il cammino è che il grafico sia connesso e abbia esattamente zero o due nodi di grado dispari. Questo risultato enunciato da Euler fu poi dimostrato da Carl Hierholzer. Un tale cammino è ora chiamato percorso euleriano o cammino di Eulero. Se ci sono nodi di grado dispari, allora qualsiasi percorso euleriano inizierà da uno di essi e finirà nell'altro. Poiché il grafico che rappresenta la storica Königsberg ha quattro nodi di grado dispari, non può avere un percorso euleriano.

Il lavoro di Eulero fu presentato all'Accademia di San Pietroburgo il 26 agosto 1735. Fu pubblicato come Solutio problematis ad geometriam situs pertinentis (La soluzione di un problema relativo alla geometria della posizione) nella rivista Commentarii academiae scientiarum Petropolitanae nel 1741. È disponibile in inglese in The World of Mathematics.

Importanza nella storia della matematica

Nella storia della matematica, la soluzione di Eulero del problema del ponte di Königsberg è considerata il primo teorema della teoria dei grafi. La teoria dei grafi è un argomento ora generalmente considerato come un ramo della combinatoria.

Stato attuale dei ponti

Due dei sette ponti originali furono distrutti durante il bombardamento di Königsberg nella seconda guerra mondiale. Altri due furono successivamente demoliti. Sono stati sostituiti da un'autostrada moderna. Gli altri tre ponti rimangono, anche se solo due di essi sono dell'epoca di Eulero (uno fu ricostruito nel 1935). Così, al 2000, c'erano cinque ponti a Kaliningrad.

In termini di teoria dei grafi, due dei nodi ora hanno grado 2, e gli altri due hanno grado 3. Quindi, un percorso euleriano è ora possibile, ma poiché deve iniziare su un'isola e finire sull'altra, è poco pratico per i turisti.

Pagine correlate

• Gioco di Icosia
• Percorso hamiltoniano
• Acqua, gas ed elettricità
• Problema del commesso viaggiatore