La teoria dei grafi, l'impalcatura matematica dietro la scienza delle reti, affonda le proprie radici nel lontano 1735 a Konigsberg, capitale della Prussia orientale, una fiorente città mercantile del suo tempo con una particolare geometria. Il commercio sostenuto dalla sua flotta permise ai funzionari della città di costruire sette ponti attraverso il fiume Pregel che circondava la città. Cinque di questi collegavano alla terraferma l'elegante isola di Kneiphof, intrappolata tra i due rami del Pregel. Questa peculiare disposizione ha dato vita a un quiz contemporaneo: si può attraversare tutti e sette i ponti senza passare due volte sullo stesso? Nonostante molti tentativi, nessuno riuscì a trovare un simile percorso. Il problema rimase irrisolto fino al 1735, quando Leonhard Euler, un matematico svizzero, offrì una rigorosa dimostrazione matematica della non esistenza di tale percorso.
Egli decise di schematizzare il problema rappresentandolo mediante un grafo: i nodi rappresentavano i lembi di terra mentre gli archi raffiguravano i ponti. Quindi Eulero fece una semplice osservazione: se c'è un percorso che attraversa tutti i ponti, ma mai lo stesso ponte due volte, vuol dire che i nodi con un numero dispari di collegamenti devono essere il punto iniziale o finale di questo percorso. Infatti, se si arriva a un nodo con un numero dispari di archi, è possibile che non si disponga di alcun collegamento ancora inutilizzato per poterlo lasciare. Il grafico di Konigsberg aveva quattro nodi con un numero dispari di collegamenti, quindi nessun percorso poteva soddisfare il problema.
Fu la prima volta in cui un grafo venne utilizzato per risolvere un problema matematico.
Nessun commento:
Posta un commento