Giro per quattro ponti – Approfondimento

Il problema proposto chiede di trovare un percorso, per la città di Bolzano, che passi una e una sola volta per quattro dei suoi ponti (il ponte Talvera, il ponte Druso, il ponte Roma e il ponte Loreto) e non utilizzi altri ponti.

Il fatto che ci siano solo vincoli sui ponti e viceversa non ci sia assolutamente nessun vincolo sul percorso che si può o si vuole fare al di fuori di questi ponti (da dove si debba passare, quanto debba essere lungo, …) ci può dare l’idea di schematizzare il problema con un grafo. In effetti, un problema simile è stato formulato anni fa a proposito dei sette ponti di Königsberg  (figura 1) sul fiume Pregel;  e la schematizzazione fornita da Eulero è uno dei primi esempi dell’uso di un grafo come modellizzazione per un problema topologico.

Il problema dei ponti di Konigsberg

Fig. 1: Il problema dei ponti di Konigsberg

In figura 2  gli archi di questo grafo (T, D, L, R) rappresentano i ponti (e sono indicati dalle rispettive iniziali), mentre i vertici del grafo (1, 2, 3) rappresentano le tre zone di Bolzano, limitate dai fiumi. Quindi, ad esempio, la zona 2 è la zona di piazza Walther, dove, dicendo “la zona di piazza Walther”, intendiamo tutti i punti della città che si possono raggiungere da piazza Walther non si attraversi nessun ponte. E questo è molto ragionevole, proprio in vista del fatto che il problema non ci pone alcun vincolo al di fuori dei ponti.

Fig.2: Grafo dei ponti

Fig.2: Grafo dei ponti

Un inciso. Spesso la matematica fa proprio questo, cioè “mette ordine” in un problema, cogliendone i punti essenziali e trovando una maniera di rappresentarlo che li metta in luce.

Allora, letto sul grafo, il problema è il seguente: si riesce a trovare un percorso sul grafo che passi, una e una sola volta, da ciascuno dei 4 spigoli, partendo dal punto 2 e ritornando al punto 2? Dopo qualche tentativo di soluzione, sembra proprio che la cosa non sia possibile (ma come giustificarlo?); è facile invece trovare un percorso che parta da 2 e termini in 1 (ad esempio, si può passare nell’ordine per i ponti L, R, D, T); come è facile trovare un percorso che inizi e termini in piazza Walther (2) se aggiungiamo anche la passerella pedonale P (vedi figura 3) di fronte al Museion: si può ad esempio percorrere nell’ordine i ponti L, R, D, T, P.

Fig. 3: Grafo dei ponti con passerella

Ma questo non ci basta!

Ci piacerebbe intanto essere sicuri che davvero nel primo caso esaminato il percorso è impossibile; e poi vorremmo capire in generale “come funziona”, cioè perché su alcuni grafi un tale percorso si può fare e per altri no; e ci piacerebbe arrivare a una risposta “universale” senza dover procedere solo per tentativi.

È abbastanza evidente che i vincoli che possono portare all’impossibilità non sono legati alla lunghezza o alla disposizione dei tratti di strada, ma piuttosto a quanti sono, e di che tipo, i punti in cui si incontrano diverse strade (se in un dato incrocio si incontrano tre strade, oppure quattro o più.

Ogni volta che si arriva in un incrocio, si deve poi uscirne percorrendo un tratto di strada diverso da quello di entrata. Perciò, se vogliamo finire la passeggiata nello stesso punto dal quale siamo partiti, in ogni incrocio devono confluire un numero pari di strade (possiamo chiamare questi punti incroci pari.

Se invece punto di arrivo e punto di partenza sono diversi, allora in questi due punti devono confluire un numero dispari di strade: dal punto di partenza si deve uscire una prima volta, e poi entrare e uscire lo stesso numero di volte, e analogamente in quello di arrivo, quindi questi percorsi comprenderanno due incroci dispari, mentre tutti gli altri incroci saranno pari.

Nel primo grafo (fig. 2), quello senza la passerella pedonale, ci sono due incroci dispari e uno pari, quindi non è possibile trovare un ciclo euleriano (che parta e arrivi nello  stesso punto), ma è possibile trovare un percorso euleriano, che parta da 2 e arrivi in 1 o viceversa.

Nel secondo grafo(fig. 3), quello che comprende la passerella pedonale di fronte al Museion, tutti i vertici sono pari e quindi riusciamo a trovare anche un ciclo euleriano, partendo da un vertice qualsiasi e ritornando al punto di partenza.

Nel (con quattro vertici e sette spigoli) che si ottiene schematizzando la situazione della città di Königsberg ci sono quattro vertici dispari e quindi non è possibile trovare né un ciclo, né un percorso euleriano.

La teoria dei grafi, di cui Eulero pose le basi, si è sviluppata soprattutto dalla metà del secolo scorso e ha numerose applicazioni in ricerca operativa, una branca della matematica che si occupa di problemi quali razionalizzare processi industriali, ottimizzare reti di distribuzione, gestire efficacemente un’impresa, ecc.

In un’altra scheda viene proposto (sempre con una passeggiata per Bolzano) un altro problema sui grafi che sembra simile, ma in realtà non lo è affatto.

pannello risposta approfondimento per la scuola link