I ponti di Konigsberg

Eulero, grande matematico del Settecento, si occupò per diversi anni della sua vita di un gioco che aprì la strada alla teoria dei grafi e alla topologia.
La città di Konigsberg, che tra l'altro diede i natali anche a Kant, era famosa per i suoi sette ponti che collegavano i vari quartieri della città; i ragazzi di Konigsberg giocavano a correre da un ponte all'altro cercando di passare una sola volta su ogni ponte.

Inutile dire che nessuno aveva trovato una soluzione, per questo aveva attirato l'attenzione di molti matematici che cercarono invano di risolvere il problema, finchè non arrivò Eulero che dimostrò che...il problema non aveva soluzione!
Cerchiamo di capire perchè. Innanzitutto trasformiamo l'immagine della città in modo che le quattro parti della città siano punti e i ponti siano delle linee che li collegano, abbiamo creato un grafo, dove i punti sono detti nodi e le linee archi. Utiliziamo prima una figura più schematica per capire meglio il grafo sotto.

Diamo due piccole definizioni:

-si dice nodo pari un nodo collegato a un numero pari di archi

-si dice nodo dispari un nodo collegato a un numero dispari di archi.

Eulero dimostrò che un grafo contenente solo nodi pari è sempre percorribile, cioè si può percorrere interamente per poi tornare al punto di partenza senza sovrapposizioni di percorso.
Invece se contiene nodi pari e solo due nodi dispari è sempre percorribile ma non si può tornare al punto di partenza.
Infine se ha tutti i nodi dispari non è più percorribile senza sovrapposizioni di percorso. Bene il problema dei ponti di Konigsberg è di questo tipo, quindi la soluzione è: non ha soluzione!