Discussione:Problema dei ponti di Königsberg

In data 7 febbraio 2011 la voce Problema dei ponti di Königsberg è stata accettata per la rubrica Lo sapevi che. Le procedure prima del 2012 non venivano archiviate, perciò possono essere trovate solo nella cronologia della pagina di valutazione.

Pagina unita a questa. --Superchilum^(scrivimi) 12:59, 15 set 2009 (CEST)[rispondi]

Non riesco a capire la numerazione dei nodi ABCD....

La sezione "Variazioni" non aveva nulla a che fare con il problema originale ed è una ricerca originale di quasi vent'anni fa, tradotta da en.wiki che ha anch'essa cancellato quel testo.

Per completezza allego qua il testo che ho tolto dalla voce.

L'enunciato originale del problema concerne vertici non identificati, cioè caratterizzati solo dai loro collegamenti. Vi sono invece variazioni su questo tema che possono essere utili per introdurre il problema nell'insegnamento e che si preoccupano di identificare i vertici del grafo con personaggi e ruoli.

Si precisa quindi che sulla riva settentrionale della città sorge lo Schloß, ovvero il castello, del principe Blu, e che sulla riva meridionale sorge quello del principe Rosso; i due principi sono fratelli, ma non sono in buoni rapporti; sull'isola orientale vi è la Kirche, la chiesa, sede del Vescovo; infine nell'isola centrale si trova una Gasthaus, un'osteria. Come si vedrà poi le relazioni fra i notabili della città, tra i quali va realisticamente considerato anche l'oste, non sono sempre facili.

Seguendo con attenzione l'ordine cronologico dei fatti, bisogna ricordare che molti abitanti della città avevano l'abitudine la sera di trattenersi alquanto alla Gasthaus e quindi di tentare l'impresa chiamata passare i ponti; alcuni poi tornavano a festeggiare la loro riuscita con ulteriori libagioni, ma senza riuscire a spiegare in modo soddisfacente come, a loro dire, vi erano riusciti e senza saper ripetere la passeggiata alla luce del giorno.

Il principe Blu, dopo aver analizzato il sistema dei ponti cittadini con l'aiuto della teoria dei grafi, si convince dell'impossibilità di passare i ponti. Decide allora di costruire di nascosto un ottavo ponte che gli permetta la sera di passare i ponti partendo dal suo Schloß e finendo alla Gasthaus dove potersi vantare della sua riuscita; e inoltre fa in modo che il principe Rosso non riesca a fare altrettanto a partire dal suo Schloß.

• Dove costruisce l'ottavo ponte il principe Blu?

Il principe Rosso, adirato per la mossa del fratello, capisce che può reagire solo dopo aver studiato la teoria dei grafi; dopo un attento studio anche lui decide di costruire di nascosto un altro ponte che consenta a lui di traversare i ponti in modo da raggiungere dal suo Schloß la Gasthaus e qui prendere per i fondelli il fratello al quale diventa impossibile passare i ponti alla sua maniera.

• Dove costruisce il nono ponte il principe Rosso?

Il Vescovo ha dovuto assistere alla dispendiosa contesa cittadina con crescente irritazione. Essa ha portato alla formazione di due facinorose fazioni e ha fatto crescere il numero degli eccessivi frequentatori della Gasthaus, con danno della quiete pubblica. Quindi anche lui, dopo un accurato studio della teoria dei grafi, decide di costruire un decimo ponte che consenta a tutti i cittadini di passare tutti i ponti e fare ritorno alla propria casa tra i tranquilli affetti familiari.

• Dove costruisce il decimo ponte il Vescovo?

Riducendo la città, come sopra, a un grafo e colorando ciascun nodo come nel problema classico, nessuna passeggiata di Eulero è possibile inizialmente. Tutti i quattro nodi hanno un numero dispari di spigoli.

Le passeggiate di Eulero sono possibili se esattamente 2 nodi posseggono un numero dispari di spigoli, che sono esattamente i nodi iniziale e finale della passeggiata. Poiché il problema presenta solo 4 nodi, tutti con grado dispari, possiamo immaginare di iniziare la passeggiata dal nodo blu e terminarla nel nodo arancione; per poter garantire la soluzione del problema, bisogna che sugli altri due nodi confluisca un numero pari di spigoli. Aggiungendo un collegamento tra essi, ci troviamo nelle condizioni del teorema di Eulero.

Risolto il problema dell'ottavo ponte, il nono ponte presenta una soluzione facile. Si richiede di utilizzare il nodo rosso come punto di partenza e l'arancione come arrivo. Per cambiare la parità dei nodi rosso e blu, si disegna un altro spigolo fra i due.

Il decimo ponte va in una direzione leggermente diversa. Il Vescovo vuole che ogni cittadino ritorni al punto di partenza. Questo è un cammino euleriano e richiede che tutti i nodi siano di grado pari. Dopo la soluzione del nono ponte i nodi rosso e arancione sono di grado dispari quindi devono essere cambiati aggiungendo un nuovo spigolo fra di loro.

-- .mau. ✉ 18:09, 4 lug 2024 (CEST)[rispondi]