La Teoria dei Grafi a partire da Königsberg

Introduco la teoria dei grafi proponendo un quesito classico, quello dei 7 ponti di Königsberg. Si dice (forse si tratta di leggenda metropolitana) che il problema se lo pose Eulero volendo cercare un itinerario circolare per una passeggiata che includesse il passaggio di tutti i ponti, ma solo una volta ciascuno. Questa è una mappa della città, costruita attorno alla confluenza di due corsi d'acqua con un'isola al centro del ramo unico.

In linea generale, per affrontare questo tipo di problema, è necessario semplificarlo con un'astrazione, concentrandosi solo sugli elementi essenziali che in questo caso sono 4 aree ben separate dall'acqua e connesse solo attraverso i ponti. Come andare da un ponte all'altro non influisce sulle nostre scelte. Indicate le aree con lettere vediamo che la A (l'isola) è raggiunta da 5 ponti, due dalla riva sud B, due da quella nord C e uno dalla lingua di terra D delimitata dai due corsi d'acqua confluenti.

Fatti un paio di tentativi, sperimentali e certamente senza esito, vi renderete ben presto conto che la soluzione non esiste. Infatti, dovunque andiate, dovreste utilizzare un ponte diverso per lasciare quell'area e visto che si richiede di passare per tutti i ponti una sola volta l'itinerario potrà essere costruito solo nel caso in cui ciascuna area abbia un numero pari di ponti. Nel caso proposto l'isola ne ha 5 e le altre tre zone solo 3, quindi tutti numeri dispari, ma ne sarebbe bastata anche solo una per avere la certezza dell'impossibilità di risolvere il problema.
Nella teoria dei grafi le aree di Königsberg sono i nodi, e i collegamenti fra essi sono indicati come archi o spigoli (nel nostro caso i ponti). Il numero di archi facenti capo ad un nodo ne forniscono il grado. La regola generale alla quale siamo appena giunti può quindi essere enunciata così: per costruire un percorso euleriano (una linea che percorra tutti gli archi una sola volta e riconduca al nodo iniziale) è necessario che tutti i nodi siano di grado pari.
In un prossimo post proporrò alcune varianti al classico quesito dei 7 ponti di Königsberg che verranno "giustificate" dall'esigenza di accontentare il Vescovo, il Principe Blu e il Principe Rosso che, volta per volta, decideranno di far costruire un nuovo ponte.
Successivamente vedremo che la teoria dei grafi si applica in una miriade di casi, dai calendari dei tornei sportivi alle scelte di percorso suggerite dal vostro navigatore stradale.
Questa nozione può tornare utile anche agli escursionisti per pianificare itinerari che prevedano il ritorno al punto di partenza evitando di ripercorrere uno stesso tratto (arco). Applicheremo la teoria per cercare di percorrere i vari sentieri di Monte San Costanzo senza tornare sui nostri passi.

NB - a partire da questo e nel corso delle prossime settimane, i post saranno sporadici (dipende da quando avrò la possibilità di collegarmi) e probabilmente  conterranno errori in quanto utilizzo il tablet, con il quale non ho eccessiva dimestichezza ed ha certamente dei limiti comparato con un computer.