La Teoria dei grafi nella città di Königsberg
4 min read
Nella storia della matematica il problema dei ponti di Königsberg è uno dei primi problemi della teoria dei grafi discusso formalmente. Lo si può anche considerare come uno dei primi problemi concernenti la topologia.
Il problema dei ponti di Königsberg
Il problema dei 7 ponti di Königsberg è un problema legato ad una reale città oggi nell’exclave russa sul Baltico, nota come Kaliningrad.
La città è percorsa dal fiume Pregel e dai suoi affluenti. Presenta due isole che sono connesse tra di loro e con le due aree principali della città tramite 7 ponti.
Il problema consiste nel poter seguire, con una passeggiata, un percorso che attraversi ogni ponte una e una sola volta. Compiendo così l’intero giro della città.
Il folklore vuole che gli stessi abitanti della città impegnassero il loro tempo per poter provare un percorso che gli permettesse di visitare la loro città secondo le regole di questo “gioco”.
Nel 1736 fu Eulero ad affrontare il problema dell’esistenza di una passeggiata che permettesse di attraversare i ponti una e una sola volta.
Approccio matematico del problema
Eulero approcciò il problema in termini di teoria dei grafi. In primo luogo astraendo dalla situazione specifica della città il problema.
I due isolotti e le due aree principali vennero schematizzati come dei punti (nodi), mentre i ponti che collegavano le varie zone vennero rappresentati come linee di collegamento tra i nodi.
Le linee non dovevano essere orientate perché i ponti non indicano un senso di percorrenza.
Inoltre non è importante come le zone vengono ridistribuite fintanto che il numero di nodi e linee che congiungono ogni punto rimangono le stesse.
Eulero concluse che:
“È possibile percorrere tutti gli archi una e una sola volta, concludendo il percorso nel nodo iniziale, se e soltanto se esce un numero pari di archi da tutti i nodi del grafo.”
Qui Eulero definisce un “Ciclo Euleriano”. Questa però non è la risposta al nostro problema per percorrere la città in quanto non dobbiamo ritornare al punto di partenza.
Risolutiva invece la conclusione:
“È possibile percorrere tutti gli archi una e una sola volta, concludendo il percorso in un punto diverso da quello iniziale, se e soltanto se esce un numero dispari di archi soltanto da due nodi oppure nessuno”.
In queste righe Eulero definisce un “Cammino Euleriano”. È possibile quindi percorrere la città di Königsberg solo se ogni nodo è collegato da un numero pari di ponti. Oppure ci sono solo due nodi con un numero dispari di ponti.
Facendo riferimento alla Fig.1 si vede che è impossibile percorrere la città di Königsberg come proposto dal problema perché tutti i nodi sono collegati da un numero dispari di ponti.
Introduzione alla Teoria dei grafi
Il problema di Königsberg trattato da Eulero è stato il primo testo a prendere in considerazione i grafi come entità matematiche.
La Teoria dei grafi è la disciplina che si occupa dello studio dei grafi, oggetti discreti che permettono di schematizzare situazioni e processi, consentendone l’analisi quantitativa.
Un grafo si definisce come un set di vertici e spigoli dove ogni spigolo è la connessione di due vertici.
Però per citare Alberto Sordi in “Il Marchese del Grillo”: “Bello, bello tutto. Adesso te ne poi andà”, a che serve questa Teoria dei grafi oltre che per risolvere un problema di quasi 300 anni fa?
Applicazioni della Teoria dei grafi
La Teoria dei grafi è una branca della “matematica pura” la cui applicabilità risiede nel non avere alcuna corrispondenza diretta con il mondo circostante.
Per questo siamo liberi di farla corrispondere, interpretarla in ogni modo scegliamo o riusciamo.
Le applicazioni più semplici le incontriamo sin da piccoli quando dobbiamo disegnare una stella passando per 5 punti.
Questa richiesta corrisponde al trovare un ciclo euleriano per cui partendo da un vertice della stella possiamo tornare allo stesso vertice.
Il risultato è possibile in quanto ogni nodo o vertice è collegato con un numero pari di spigoli. Nello specifico sappiamo che i cammini sono 5: uno per ogni vertice della stella.
Un altro esempio un po’ più complicato sono i sudoku, che allo stesso modo si possono risolvere con un algoritmo ben noto nella teoria dei grafi.
Sviluppi importanti si hanno anche nell’ambito della bioinformatica dove la teoria dei grafi viene impiegata per la sintesi di stringhe di DNA.
Partendo da stringhe di frammenti di DNA, formati dalle 4 basi A,T,G,C, si è visto possibile ricostruire un intero genoma, riducendo la percentuale di errori rispetto ai risultati ottenuti con le precedenti tecniche.
Inoltre la teoria dei grafi è pesantemente utilizzata nel mondo dei social network dove ogni “nodo” rappresenta un profilo e gli “spigoli” sono i legami virtuali che si stringono. Ad esempio gli amici consigliati vengono mostrati in base ai contatti che hanno i vostri amici e quindi in base a quanti “spigoli” creano le persone che conoscete con altri “nodi”.
Non è proprio per tutti
L’applicabilità di questa teoria, come per la “matematica pura” sta principalmente nell’ occhio dell’ osservatore. Seppur astratta e di difficile comprensione, rimane comunque una teoria estremamente affascinante.
Se non particolarmente interessati allo studio della matematica più “pesante” questa teoria, nelle sue applicazioni più banali, rimane sempre un buon modo per passare un’ora di svago davanti al caminetto provando a trovare le soluzioni a piccoli indovinelli.
Ad esempio, collegati al problema di Königsberg, è possibile provare trovare soluzione ai problemi di : Il settimo ponte del principe Blu, l’ottavo ponte del principe Rosso e il decimo ponte del Vescovo.
Buon divertimento!
Laureato in Fisica e attualmente studente alla Magistrale in Physics a Camerino. Sono costantemente in cerca di nuovi stimoli e sempre in prima linea quando si tratta di imparare qualcosa di nuovo. Avvicinare le persone al mondo della Fisica e della Matematica è uno dei miei obbietivi, così che tutti possano capire meglio il mondo che li circonda e il linguaggio con cui esso è descritto.
