Problema dei ponti di Königsberg: differenze tra le versioni

Eulero rappresentò la disposizione dei sette ponti congiungendo con altrettante linee le quattro grandi zone della città, come nella prima immagine. Si noti che dai nodi A, B e D partono (e arrivano) tre ponti; dal nodo C, invece, cinque ponti. Questi sono i gradi dei nodi: rispettivamente, 3, 3, 5, 3. <br /> Prima di raggiungere una conclusione, Eulero ha ipotizzato delle situazioni diverse di zone e ponti (nodi e collegamenti): con quattro nodi e quattro ponti è possibile partire, ad esempio, da A, e tornarci passando per tutti i ponti una e una sola volta. Il grado di ciascun nodo è un numero pari. Se invece si parte da A per arrivare a D, ogni nodo è di grado pari a eccezione di due nodi, di grado dispari (uno). Sulla base di queste osservazioni, Eulero ha enunciato il seguente teorema:

:''Un qualsiasi grafo è percorribile se e solo se ha tutti i nodi di grado pari, o due di essi sono di grado dispari; per percorrere un grafo "possibile" con due nodi di grado dispari, è necessario partire da uno di essi, e si terminerà sull’altro nodo dispari''.

Pertanto è impossibile percorrere Königsberg come richiesto dalla tesi, poiché tutti i nodi sono di grado dispari.

 

Riduci la città, come sopra, a un [[grafo]]. Colora ciascun [[nodo (grafi)|nodo]] come nel problema classico, nessuna passeggiata di [[Eulero]] è possibile. Tutti i quattro nodi hanno un numero dispari di [[spigolo|spigoli]].

 

 

==== L'ottavo ponte del Principe Blu ====

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, la passeggiata inizia nel nodo blu e termina nel nodo arancione. Bisogna quindi disegnare un nuovo spigolo fra gli altri due nodi. Poiché hanno formalmente un numero dispari di spigoli, bisogna creare un numero pari di spigoli in tutti i nodi che non siano quello iniziale e finale. Un cambiamento nella [[Numeri pari e dispari|parità]] da grado dispari a grado pari. Sarebbe altrimenti bastato erigere un ponte che partisse dal bianco all'arancione. In questo modo solo due punti avevano un numero dispari di ponti.

 

==== Il nono ponte del Principe Rosso ====