Alessandro La Farciola

Nel mondo della matematica: i ponti di Kӧnigsberg

Il problema dei ponti di Kӧnigsberg è uno dei primissimi problemi della teoria dei grafi che nel corso del 1700 è stato discusso formalmente in ambiente matematico.  Esso nasce da una situazione concreta di una città reale. Kӧnigsberg, l’attuale Kaliningrad, in Russia, era una città della Prussia orientale percorsa da un importante fiume e alcuni suoi affluenti. Per permettere la comunicazione tra i vari quartieri della città sono stati costruiti sette ponti, come nella figura in alto.

È nato così un interrogativo comune: è possibile con una passeggiata percorrere tutti e sette i ponti attraversandoli una e una sola volta?

Ad una domanda così semplice non corrisponde una soluzione altrettanto semplice. Anche se qualcuno all’epoca provava empiricamente a trovare una risposta, camminando per ore nel centro di Kӧnigsberg, formalmente la soluzione è stata dimostrata da Eulero nel 1741, sfruttando importanti e generali risultati della teoria dei grafi. Il problema, infatti, si può schematizzare come un grafo, ovvero un insieme di nodi che possono essere collegati tra loro attraverso degli archi, diventando come nell’immagine seguente.

In generale Eulero stabilì che:

  • Un grafo composto da nodi collegati da un numero pari di archi (nodi di ordine pari) può essere attraversato passando una e una sola volta per tutti i nodi, tornando così al punto di partenza.
  • Un grafo che contiene nodi di ordine pari e solo altri due collegati con un numero dispari di archi (nodi di ordine dispari) può essere percorso, ma bisogna partire da uno dei due nodi di ordine dispari e arrivare necessariamente all’altro nodo di ordine dispari.
  • Un grafo, infine, che contiene più di due nodi di ordine dispari non può essere percorso interamente senza attraversare archi già toccati in precedenza.

Allora qual è la soluzione del problema originario? Analizzando attentamente il grafo che schematizza la città di Kӧnigsberg con i suoi ponti, si può osservare che esso contiene quattro nodi aventi tutti ordine dispari.

Il problema, quindi, risulta impossibile.

Alessandro La Farciola

Redazione

CBlive

Articoli Correlati

Lascia un commento

Back to top button

Preferenze sulla privacy

Necessari

— HTTP Cookie di navigazione www.cblive.it
Cookie strettamente necessari devono essere abilitati in ogni momento in modo che possiamo salvare le tue preferenze per le impostazioni dei cookie.
Se disabiliti questo cookie, non saremo in grado di salvare le tue preferenze. Ciò significa che ogni volta che visiti questo sito web dovrai abilitare o disabilitare nuovamente i cookie.

_gid

Google Analytics

— Google Analytics
— Google Analytics tracking cookie
Questo sito Web utilizza Google Analytics per raccogliere informazioni anonime come il numero di visitatori del sito e le pagine più popolari. Mantenere abilitati questi cookie ci aiuta a migliorare il nostro sito web

_ga,_gat

Google Adwords

Da Google -- Per aiutare i nostri partner a gestire la loro pubblicità e i loro siti web, offriamo molti prodotti, fra cui AdSense, AdWords, Google Analytics e una serie di servizi di DoubleClick. Quando visiti una pagina o visualizzi un annuncio che utilizza uno di questi prodotti, sui servizi Google o su altri siti e app, al tuo browser potrebbero essere inviati alcuni cookie.

I cookies possono essere impostati da diversi domini tra cui google.com, doubleclick.net, googlesyndication.com, o googleadservices.com, o il dominio dei siti dei nostri partners. Alcuni dei nostri prodotti pubblicitari permettono ai nostri partners di usare altri servizi integrandoli ai nostri ( come ad esempio un misuratore di pubblicità e un servizio di segnalazione), e questi servizi possono inviare il loro cookies al tuo browser. Questi cookies saranno impostati dai loro domini.

https://policies.google.com/technologies/ads?hl=it
https://support.google.com/adwordspolicy/answer/

test_cookie

error: Contenuto protetto !!
Close