Pagina 1 di 1

I ponti di Konigsberg

Inviato: 30 lug 2009, 10:44
da Giuseppe R
Dimostrare che il problema dei ponti di Konigsberg non ha soluzioni.

Per chi non lo sapesse, bisogna attraversare tutti i ponti una e una sola volta passando per tutte le zone dell'isola e tornando al punto di partenza.
http://it.wikipedia.org/wiki/File:7_bridges.svg

Mi chiedevo se c'è una soluzione che non riguarda la teoria dei grafi, ma non l'ho trovata. Voi che dite?

Inviato: 30 lug 2009, 11:06
da Ani-sama
Onestamente mi stupirebbe una soluzione che non passasse per la teoria dei grafi, ma per il semplice fatto che non mi viene in mente proprio nessun altro framework nel quale impostare il problema... può darsi che sia ignoranza mia, comunque!

La soluzione che fa uso della teoria dei grafi, in ogni caso, è una conseguenza diretta delle più basilari proprietà dei grafi euleriani. :)

Inviato: 30 lug 2009, 12:56
da Tibor Gallai
Non appena dai al problema un senso matematico, ovvero lo modellizzi nei modi più ovvi, lo riduci ad un problema su grafi o qualcosa di banalmente equivalente.
Inoltre, essendo un problema per sua natura finito, nel senso che per la sua soluzione sufficie l'esame di un numero finito (e piuttosto piccolo) di elementi, non è necessario ricondurlo al teorema di Eulero, o altre cose molto generali.

Inviato: 30 lug 2009, 13:07
da edriv
Ani-sama, sarà anche vero che ogni soluzione passa per la teoria dei grafi, ma la soluzione la si può spiegare anche ad un beduino che di matematica non sa niente...

Ci sono quattro isole. Escluse la partenza e l'arrivo, restano almeno due isole, consideriamone una. La prima volta che ci passo, ci entro camminando per un ponte. Poi dovrò uscire per un altro ponte. C'è un terzo ponte da percorrere che dà su quell'isola, però dopo che ci sono entrato, non potrò più uscire, perchè ora ho già usato tutti i ponti! Ma quell'isola l'ho scelta in modo che non fosse la fine del mio percorso! Quindi fare il percorso completo è impossibile.