I ponti di Königsberg e la nascita della teoria dei grafi
Negli anni ‘70 una ventata di rinnovamento investì l’insegnamento della matematica. Molti ricorderanno gli entusiasmi che la teoria degli insiemi, la cosiddetta insiemistica, riuscì ad accendere allora. Purtroppo, un suo uso improvvido in chiave didattica fece sì che tutto finisse in una bolla di sapone. E questa importante disciplina fu di fatto bandita dall’insegnamento. Però lo stato di degrado in cui ora versa l’apprendimento della matematica è sotto gli occhi di tutti. È quindi essenziale riesaminare le tematiche proposte ai nostri ragazzi, anche recuperando alcuni argomenti di un tempo, troppo precipitosamente cancellati dall’insegnamento; avendo come primario obiettivo quello di educare alla razionalità. Altrimenti, come Umberto Eco ebbe a scrivere alcuni anni fa sul Corriere della Sera, il prossimo stadio verso cui l’umanità si evolverà sarà quello dell’ “Homo stupidus stupidus”.
Tra i temi da presentare agli studenti, quello della teoria dei grafi ha una notevole importanza, sia da un punto di vista applicativo, sia dal punto di vista dell’avvio al ragionamento matematico. Qui di seguito illustreremo quelli che furono i primi passi nell’ambito di questa disciplina, nonché una proposta di semplificazione – in cui si fa uso del gioco del domino – per la discussione del classico problema sulla percorribilità dei ponti di Königsberg, che Eulero dimostrò essere irrisolubile.
Però la facile dimostrazione di Eulero ha per un non matematico il “difetto” di essere condotta in termini non sufficientemente concreti. Ed è per questo che a Königsberg pare che ci siano ancora delle persone che, non del tutto convinte del risultato di Eulero, cercano di fare quel percorso impossibile. Il che è un indice preoccupante del fatto che anche gli aspetti più elementari della matematica spesso hanno difficoltà a diventare patrimonio comune, non solo in Italia.
Agli inizi del 18° secolo gli abitanti di Königsberg (l’odierna Kaliningrad, situata nella Prussia del nord, presso il mar Baltico) avevano un problema semplice da enunciare, che però non riuscivano a risolvere. La citta è attraversata dal fiume Pregel e sorge in parte su due isole, oltre le quali il fiume si getta in mare. A quei tempi le due isole e le altre sponde del fiume erano collegate con sette ponti, come si può rilevare dallo schizzo di Fig. 1 (è lo stesso che Eulero presentò nell’articolo da lui dedicato al problema). Ebbene, gli abitanti di Königsberg si domandavano se fosse possibile compiere un cammino (cioè, una passeggiata) lungo quei ponti in modo tale da percorrerli una volta soltanto (cammino semplice) senza tralasciarne alcuno. Eulero, introducendo la teoria dei grafi, provò che il quesito aveva risposta negativa, dando una condizione necessaria di risolubilità per problemi di quel tipo, che nel caso di Königsberg non è soddisfatta.
Eulero risolse il problema rappresentando le quattro zone della città su cui arrivavano i sette ponti con dei punti chiamati nodi (o vertici); si veda Fig. 2, dove i quattro nodi sono denotati con i numeri 1, 2, 3, 4. Inoltre ciascun ponte fu rappresentato da una linea (chiamata lato, o spigolo) che congiungeva i due nodi che denotavano le due zone collegate dal ponte considerato. Schemi di questo tipo prendono il nome di grafi. Il numero di lati che terminano su di un nodo e detto grado di quel nodo. Ai grafi si trasferiscono immediatamente le nozioni di “cammino” e di “cammino semplice”, intesi come percorsi lungo gli spigoli, da affrontare l’uno dopo l’altro senza “salti”; cioè, nel caso di una rappresentazione grafica, da percorrere con un solo tratto di penna. Perciò il problema di Königsberg si traduce in quello di effettuare un cammino semplice lungo tutti i lati del grafo di Fig. 2.
Ebbene, Eulero dimostrò che quel cammino non si può effettuare qualora un grafo abbia più di due nodi di grado dispari (impedimento di Eulero), come nel caso di Königsberg. Perciò quel cammino non si può effettuare nemmeno nel caso del grafo di fig. 3 – ben noto agli appassionati di quiz – dato che esso ha il solo nodo centrale di grado pari, mentre gli altri quattro hanno tutti grado 3.
Usando il gioco del domino è facile vedere che la famosa passeggiata di Königsberg non si può fare. In un secondo momento lo stesso tipo di impostazione si può usare per discutere il caso generale.
Osservando Fig. 2, ci si rende conto che gli spigoli – e quindi i sette ponti della città – si possono rappresentare con le seguenti tessere del gioco del domino; ad esempio, la prima tessera rappresenta uno dei due spigoli che congiungono il nodo 1 col nodo 3.
Ricordiamo che un allineamento di quelle tessere, fatto rispettando la regola del domino, richiede che due di queste possano essere consecutive solo quando un numero dell’una è accostato allo stesso numero presente sull’altra. Perciò un numero presente soltanto all’interno dell’allineamento ha sempre delle presenze che sono in numero pari (naturalmente una delle tessere che allineiamo può essere capovolta rispetto alla presentazione precedente (come, ad esempio, la prima tessera qui sotto).
Nell’allineamento sottostante il numero 1 (espresso da un puntino) ha due coppie di presenze, mentre il 2 (espresso da due puntini) ha una coppia di presenze. Invece i numeri 3 e 4, che hanno ciascuno una presenza anche in un estremo dell’allineamento, hanno un numero dispari di presenze.
Notiamo che a ogni cammino lungo gli spigoli del grafo di Fig. 2 possiamo far corrispondere un allineamento delle tessere del domino che rispetti le regole di quel gioco. Ad esempio, l’allineamento presentato poc’anzi esprime proprio il cammino costituito dallo spigolo che va dal nodo 3 al nodo 1, seguito da quello che va dal nodo 1 al nodo 4, che a sua volta è seguito dallo spigolo che va dal nodo 4 al nodo 1, e così via.
Ora supponiamo, per assurdo, che il famoso cammino a Königsberg si possa fare, onde a esso corrisponde un allineamento delle sette tessere. Ebbene, in quell’allineamento almeno due numeri sono presenti soltanto all’interno dell’allineamento (agli estremi sono disponibili solo due posti!). Fissiamo l’attenzione su uno di questi numeri e chiamiamolo a.
Per quanto è stato già detto, a nell’allineamento ha un numero pari di presenze. Nello stesso tempo a è presente tante volte quante sono le tessere in cui esso figura (ricordiamo che c’è una tessera per ogni spigolo); cioè, tante volte quanti sono gli spigoli che toccano a. E questi sono in numero dispari, dato che ogni nodo del grafo di Fig. 2 ha grado dispari. Il che è assurdo. Perciò il cammino non si può fare.
Fine del problema!
Nota Bene. Con un po’ di attenzione si vede che il discorso si può ripetere per un qualsiasi grafo che abbia più di due nodi di grado dispari. Infatti – avendo indicato ciascun nodo con un numero e traducendo il problema in termini di gioco del domino – poiché i nodi di grado dispari sono più di due e le posizioni agli estremi sono soltanto due, uno di questi nodi sarà rappresentato da un numero che nell’ipotetico allineamento di tessere può essere presente solo all’interno di un allineamento, quindi un numero pari di volte. Ciò – come per Königsberg – è in contrasto col fatto che quel nodo abbia grado dispari.
Viceversa, si può provare che, dato un grafo quasi-connesso (cioè, che si presenti come un blocco unico, a parte l’eventuale presenza di nodi su cui non arrivino spigoli: nodi di grado 0. In termini più precisi ciò vuol dire che, dati due nodi distinti e di grado diverso da 0, onde su di essi arriva uno spigolo, c’è un cammino che li collega. Un grafo quasi-connesso che sia privo di nodi di grado 0 è detto connesso.), se l’impedimento di Eulero non c’è, allora il cammino semi-euleriano esiste sempre; inoltre, si può darne una costruzione. Però questo è un po’ più complicato da vedere; perciò lo riserviamo a un’esposizione più estesa dell’argomento.
Articolo completo scaricabile in PDF
Domenico Lenzi