144. I sette ponti di Kaliningrad

Il problema dei sette ponti di Königsberg è un problema ispirato da una situazione concreta. Königsberg, un tempo in Prussia Orientale (sul Baltico) e oggi nota con il nome di Kaliningrad, è percorsa dal fiume Pregel e dai suoi affluenti; 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 e tornare al punto di partenza. Nel 1736 Leonhard Euler affrontò tale problema, dimostrando che la passeggiata ipotizzata non era possibile.

 

 

A Königsberg sono nati molti illustri filosofi e scienziati:

• Christian Goldbach (1690-1764) matematico, autore dell'omonima congettura sui numeri primi
• Immanuel Kant  (1724-1804) filosofo illuminista, autore della Critica della ragion pura
• Gustav Robert Kirchhoff (1824-1887) fisico e matematico
• Alfred Clebsch (1833-1872) matematico
• David Hilbert (1862-1943) matematico
• Arnold Sommerfeld (1868-1951) fisico

All'Università di Königsberg, conseguì la laurea nel 1885 Hermann Minkowski (1864-1909) che, mentre era ancora studente, nel 1883 venne insignito del Premio della Matematica dell'Académie des Sciences francese per il suo manoscritto sulla teoria delle forme quadratiche. Minkowski insegnò presso le Università di Bonn, Gottinga, Königsberg e Zurigo. A Zurigo, fu uno degli insegnanti di Albert Einstein.

Dell’importanza di Minkowski per la fisica si parlerà in uno dei prossimi post e se n’è già accennato nel precedente:

http://zibalsc.blogspot.it/2011/01/15-spaziotempo-di-minkowski.html

 

Il problema dei ponti di Königsberg è forse il primo problema topologico risolto.

Il metodo inventato da Eulero si basa su un modo di rappresentare i percorsi.

Si comincia con l'indicare con A, B, C e D le quattro regioni. Si indicano poi con a, b, c, d, e, f, g  i sette ponti.

Scrive Eulero:

“se il viaggiatore dovesse partire dalla regione A e, attraverso non importa quale dei ponti a o b, si recasse in B, indicherò il suo percorso con AB; se poi si recasse in D, il nuovo tratto lo indicherei con BD e tutto il tragitto con ABD. Se poi andasse da D a C, allora il percorso complessivo diventerebbe ABDC. Le quattro lettere ABDC dicono non solo qual è stato il percorso, ma dicono anche che sono stati attraversati tre ponti. In generale, il numero di ponti attraversati è di uno minore del numero di lettere MAIUSCOLE utilizzate per il percorso.

Viceversa, se si transita su un certo numero di ponti, allora il numero di lettere MAIUSCOLE sarà di uno maggiore di quelle minuscole.”

Ecco la prima considerazione: il percorso cercato dovrà essere costituito da otto lettere MAIUSCOLE - perché i ponti, sui quali si deve passare una sola volta, sono sette.

Risolvere il problema si riduce a trovare la parola giusta: se la parola non esiste, è inutile cercare il percorso.

Eulero prosegue analizzando che cosa può capitare alla lettera A.

Se la regione A fosse collegata a un'altra regione con un solo ponte, allora la parola conterrebbe una sola volta la lettera A, sia che si parta da A sia che si parta da un'altra regione.

Se la regione A fosse collegata con altre regioni con tre ponti, allora la parola conterrebbe due volte la lettera A, sia che si parta da A sia che si parta da un'altra regione.

Se la regione A fosse collegata con altre regioni con cinque ponti, allora la parola conterrebbe tre volte la lettera A, sia che si parta da A sia che si parta da un'altra regione.

In generale, se una regione è collegata ad altre con un numero dispari di ponti, la sua lettera apparirà tante volte secondo la regola: metà del numero di ponti aumentato di uno. Nel nostro caso, poiché A è collegata alle altre regioni con cinque ponti, la lettera A dovrà apparire tre volte nella parola; poiché la regione B è collegata alle altre con tre ponti, la lettera B dovrà apparire due volte, come, per lo stesso motivo, le lettere C e D. In totale, nella parola di otto lettere, dovranno apparire tre A, due B, due C e due D,

ma 3 + 2 + 2 + 2 = 9, e quindi non esiste una soluzione.

 

La regola generale trovata da Eulero è la seguente:

 

“se sono più di due le regioni alle quali conducono un numero dispari di ponti, allora si può affermare con certezza che la passeggiata è impossibile;

è invece possibile se sono solo due le regioni alle quali conducono un numero dispari di ponti (a condizione che si parta da una di esse) oppure se a nessuna regione giunge un numero dispari di ponti (qualunque sia la regione dalla quale si parte).”

Contrariamente a quanto si crede, Eulero non ricorse ai grafi, anche se ne ispirò la scoperta.

http://it.wikipedia.org/wiki/Problema_dei_ponti_di_K%C3%B6nigsberg

 

“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 (v. Storia della combinatoria).”