Fra gioco e applicazione /1: quel tour di Eulero che arriva fino alla robotica e alla genetica

C’è un meccanismo formidabile nella cultura occidentale: si accumula conoscenza per il gusto di sapere, poi questo patrimonio dà frutti inaspettati in aree lontane. Questo è molto frequente in matematica: un ingegnere, un astronomo, un fisico ha un’idea con cui risolve un suo problema pratico; poi un matematico la generalizza, ne fa una teoria strutturata.

Sul momento questa astrazione pare inutile, fine a se stessa. Però più tardi qualcun altro utilizza proprio la generalità della teoria per un’applicazione lontanissima dal problema originario. Alle volte l’innesco è addirittura ludico: un indovinello, un gioco. Dedico i prossimi post a storie di questo tipo.

Königsberg era una città della Prussia Orientale adagiata sulle due rive e su due isole del fiume Pregel; i collegamenti erano garantiti da sette ponti (vedi a sinistra nella figura). Oggi, col nome di Kaliningrad, è un’enclave della Federazione russa e ha più ponti di allora. Nel 1736 nelle bettole della città gira un quesito: è possibile compiere una passeggiata che attraversi ogni ponte una sola volta e ti riporti al punto di partenza? Nessuno riesce a progettare un tale giro, ma nessuno sa dimostrare che sia impossibile.

Il sindaco della vicina Danzica ha un’idea: chiedere lumi al grande matematico, Leonhard Euler. Subito la risposta è cortese ma un po’ irritata: sostanzialmente “questa non è matematica”. Ahimè, questa è una frase che mi tocca sentire troppo spesso da certi finti geni a proposito di nuovi spunti della nostra disciplina. Ma Eulero è un genio vero: si appassiona al problema e lo risolve con un teorema che possiamo considerare il primo di una nuova parte della matematica: la teoria dei grafi*.

La formalizzazione corrente della teoria dei grafi è del secolo successivo; nel ventesimo secolo, poi, la teoria ha uno sviluppo enorme, data la sua plasticità nel rappresentare situazioni applicative. In particolare, la teoria si presta a studiare problemi di ottimizzazione.

Uno di questi – proprio legato al teorema di Eulero – è il “problema cinese del postino”, formulato da Kwan Mei-Ko nel 1960: un portalettere deve consegnare la posta nel suo quartiere; vuole minimizzare il suo percorso, tenendo conto del fatto che deve percorrere ogni strada del quartiere almeno una volta. Se il grafo costituito dalle strade e dai loro incroci è euleriano (cioè se esiste un tour di Eulero che percorra ogni strada esattamente una volta), allora ogni tour di Eulero è un percorso minimo. Ma, in generale, il grafo non è euleriano; perciò la soluzione consiste nell’”eulerizzare” il grafo sdoppiandone certi lati, cioè individuando un insieme ottimale di strade da percorrere due volte.

Questo, in fin dei conti, può apparire un problema molto limitato: va là che un portalettere il suo percorso minimo lo individua anche senza teorie matematiche! Il punto è che lo stesso tipo di ottimizzazione investe altre situazioni di cui quella del postino è un esempio. Un problema simile è quello dell’esplorazione, da parte di un robot mobile, di una rete di strade sconosciuta. Una situazione più astratta è quella in cui i vertici sono gli stati di uno smartphone e due vertici sono collegati se e solo se c’è fra loro un passaggio diretto costituito dal pigiare un tasto, e si vuole organizzare il controllo delle funzionalità.

Ma l’applicazione più sorprendente è in genetica: si usano tour di Eulero per mettere insieme frammenti di Dna (Pevzner, P. A., Tang, H., & Waterman, M. S., An Eulerian path approach to DNA fragment assembly, Proc. of the National Academy of Sciences, 98(17) (2001), 9748-9753). Così da un problema popolare si è arrivati alla robotica e alla biotecnologia. Ma non è un caso isolato di gioco-matematica-applicazione. Ne vedremo degli altri.

*Un grafo è una struttura matematica costituita da vertici (di solito rappresentati da punti), da spigoli e da una funzione di incidenza che assegna ad ogni spigolo una coppia di vertici (che saranno rappresentati uniti da un arco di curva). Il grado di un vertice è il numero di spigoli che incidono su quel vertice. Il teorema di Eulero dice: “In un grafo esiste un percorso chiuso, che percorre ogni spigolo esattamente una volta, se e solo se ogni vertice ha grado pari”. Rappresentando ogni riva e ogni isola di Königsberg con un vertice e ogni ponte con uno spigolo, si ottiene il grafo rappresentato a destra nella figura. Si può allora verificare che la condizione del teorema non è soddisfatta, il che dimostra che il tour cercato non esiste.