Eulero ed il problema dei Ponti di Königsberg
Nella formulazione di un problema si constata spesso la convenienza a rappresentare geometricamente gli elementi in gioco mediante punti (o cerchietti, quadratini...) collegati tra loro da linee o frecce. I punti possono rappresentare, a seconda del contesto, oggetti, persone, compiti da assegnare e così via; le linee esprimeranno invece l'esistenza, tra certe coppie di punti, di relazioni. Questo strumento, fondamentale in molti problemi di ottimizzazione, va sotto il nome di grafo.
La teoria dei grafi è stata “inventata” più volte. Si usa far risalire la sua data di nascita al matematico svizzero Leonardo Eulero, considerato il più importante matematico del Settecento, che pubblicò il suo primo lavoro sui grafi nel 1736. Obiettivo di Eulero era la risoluzione del famoso problema dei 'ponti di Kőnigsberg'. La città, oggi Kaliningrad, situata allora nella Prussia Orientale, sorge su di un fiume e include due isole collegate tra loro e con le altre sponde del fiume da 7 ponti. Ci si chiedeva se fosse possibile partire da una qualunque delle quattro zone in cui risultava naturalmente divisa la città, attraversare ogni ponte esattamente una volta e tornare al punto di partenza.
Immagine tratta da: www.lanostra-matematica.org
Eulero sostituì ogni zona con un punto ed ogni ponte con una linea ottenendo un grafo. Il problema diventava quello di vedere se fosse possibile percorrere tutte le linee del grafo sequenzialmente, ciascuna una sola volta, e tornare al punto di partenza.
Da buon matematico egli generalizzò la questione ed individuò un criterio per decidere se è percorribile (nel senso appena detto) un grafo qualunque: il grafo deve essere connesso - cioè ogni punto deve essere raggiungibile - e da ogni punto deve uscire un numero pari di linee.
Eulero dimostrò che il problema dei ponti di Königsberg era impossibile!
Nota personale: si potrebbero sempre costruire due ponti per unire AC e BD...
* ispirato da: 'Lezioni di Ricerca Operativa' – F. Mason
______________________________
