Matematica, lezione 28: La teoria dei grafi

Storicamente la teoria dei grafi muove i primi passi grazie alla risoluzione del problema dei sette ponti di Konigsberg da parte di Leonhard Euler, o Eulero per gli amici italiani. Sonia Carras e Ludovico Pernazza, dopo aver introdotto storicamente la teoria e tutti i suoi elementi cardine, inclusa l'equazione di Eulero relativa a spigoli, vertici e facce, passa a proporre una serie di applicazioni pratiche della teoria, come per esempio la risoluzione del problema del trasporto ottimale delle merci lungo una rete o della gestione dei voli aerei tra un insieme di aereoporti.
Tra le applicazioni più interessanti, però, ci sono quella relativa agli scacchi (e non escludo che utilizzerò la bibliografia relativa per una serie di post scacchistici su cui sto ragionando), quella relativa al calcio (cui dedicai alcuni anni fa alcuni post su Science Backstage) e infine quella in qualche modo sorprendete applicata alla musica. Tra l'altro i due autori citano anche Moreno Andreatta e il suo volume dedicato all'argomento, il 13.mo della collana, che se ricordate bene pensavo sarebbe stato più opportuno far uscire un po' più avanti nel corso della collana. In particolare i due autori ricordano come Andreatta non solo utilizza la teoria dei grafi per classificare la musica, ma anche per comporre musica nuova, il che, in qualche modo, dimostra ancora una volta come ci sia ben poco da stupirsi se, finalmente, le reti neurali sono oggi in grado di comporre musica in grado di rientrare entro i canoni, matematicamente classificati, della musica mondiale.

Rompicapi di Alice: Generatore di labirinti

Avevo già affrontato l'argomento dei labirinti in un lontano Rompicapo, e ho pensato bene di tornare sull'argomento però da un punto di vista leggermente diverso: gli algoritmi di generazione dei labirinti.
Per generare un labirinto si parte da una griglia di celle, generalmente rettangolare, ma se ne può realizzare una di qualsiasi forma. A questa griglia si associa un percorso in cui i nodi coincidono con il centro di ciascuna cella. Lo scopo del generatore di labirinti è quello di determinare un sottografo in cui sia difficile trovare l'unico percorso che collega due nodi particolari, denominati ingresso e uscita.
Poiché la mappa del labirinto è, di fatto, un albero, ovvero un percorso che unisce un insieme di punti connessi a due a due da una e una sola linea, gli algoritmi di generazione ricadono nel campo della teoria dei grafi. Di tutti i possibili algoritmi (ce ne sono diversi) vi propongo quello basato sull'algoritmo di Kruskal, proposto nel 1956 da Joseph Kruskal⁽²⁾, fratello di Martin David⁽¹⁾. L'algoritmo si compone di questi passi:

Urschel: un grande matematico sui campi da football

La comunità matemtica è una comunità che rispetto molto. Ho il profondo desiderio di essere accetato in essa, e accettato come un membro legittimo.⁽¹⁾

John Urschel, foto di Shawn Hubbard

John Urschel è un giocatore di football americano, un ragazzo canadese imponente che gioca per i Baltimore Ravens nella National Football League, dove ha esordito nel 2014 giocando nel ruolo di guardia. Urschel, però, ha anche qualcosa in comune con un quarterback texano, Frank Ryan⁽¹⁾, che nel 1965 ottenne il Ph.D. in matematica, pubblicando peraltro un paio di articoli sulle funzioni olomorfe, e insegnando matematica alla Rice. Avrete già immaginato che Urschel ha intrapreso il duro cammino di un Ph.D. in matematica, scegliendo il MIT come college, dove si sta interessando di teoria spettrale dei grafi, algebra lineare numerica e machine learning. Urschel gioca con il numero 64, tra le tante cose numero pari, difettivo, numero colombiano e, soprattutto, numero potente, come dovrebbe essere un giocatore di football americano. E’ anche un appassionato giocatore di scacchi (vedi ad esempio la partita sua e di Danny Rensch contro il mondo!)

I rompicapi di Alice: Il problema dei servizi

"Inizia dall'inizio", disse il Re con gravità, "e vai fino a che non arrivi alla fine; quindi fermati"
Lewis Carroll da Alice nel Paese delle Meraviglie

La teoria dei grafi inizia con la risoluzione di un problema di geometria reale. Il geniale matematico svizzero Eulero, infatti, propose in un famoso articolo⁽¹⁾ la soluzione di un rompicapo basato sulla città di Konigsberg e i suoi sette ponti:

(via David Galvin - pdf)

la cittadina prussiana è tagliata dal fiume Pregel al cui centro si trovano due isole raggiungibili attraverso sette ponti; è dunque possibile trovare un percorso chiuso (punto di inizio e punto di fine coincidono) in grado di attraversare tutti i sette ponti una e una sola volta?

All'interno dell'articolo⁽¹⁾, arricchito anche di precise illustrazioni, Eulero sviluppa le basi di quella che sarà la meglio nota teoria dei grafi, e che può essere così riassunta:
Un grafo, o reticolo, è una figura bidimensionale caratterizzata da due elementi: i nodi, ovvero dei punti di passaggio obbligatori, e gli archi, ovvero le linee che congiungono i nodi. I primi si distinguono tra nodo pari, ovvero un punto in cui converge un numero pari di archi, e nodo dispari, ovvero un punto in cui converge un numero dispari di archi. Un reticolo euleriano è, quindi, un reticolo contenente nodi pari o al più due nodi dispari. Un reticolo euleriano è completamente percorribile (e può essere disegnato) senza mai staccare la penna dal foglio, partendo da un dato nodo e finendo alla fine su di esso. Si distinguono, poi, due generi di reticoli euleriani: quello chiuso e quello aperto, dove per chiuso si intende un reticolo che inizia e finisce sullo stesso nodo, mentre uno aperto che inizia e finisce su un nodo differente. Si avrà un reticolo chiuso quando tutti i nodi sono pari, si avrà un cammino aperto quando ci saranno due nodi dispari, uno come partenza della nostra camminata lungo il reticolo e l'altro come conclusione. Eulero dimostrò che nel caso di Konigsberg il reticolo era (e continua ad esserlo ancora oggi, nonostante l'aggiornamento dei ponti) né aperto né chiuso, rispondendo quindi negativamente alla domanda iniziale⁽⁴⁾.
Il problema dei servizi, che mi venne posto qualche anno fa, è anch'esso uno di quei problemi o rompicapi che può essere analizzato utilizzando la teoria dei grafi; questo un suo possibile enunciato:

Bisogna collegare, su una superficie planare, tre case ai tre servizi essenziali di acqua, luce e gas senza che i tubi di collegamento si intersechino tra loro.

Apparentemente questo problema è di facile risoluzione e presenta tutta una serie di rompicapi equivalenti (il più truculento è quello detto della vendetta Corsa), ma la sua prima risoluzione, così come ci è stata tramandata, su carta stampata risale al 1917 e porta la firma di Henry Ernest Dudeney, sulle pagine del suo Amusements in Mathematics. Il rompicapo, però, sembra fosse noto ben prima di Dudeney: secondo Sam Loyd jr., il padre lo aveva scoperto già nel 1900, ma non lo aveva inventato lui, come anche molti storici della matematica sostengono⁽³⁾.
In effetti un problema topologicamente simile ci è stato tramandato direttamente dall'antica Persia:

Un califfo era così turbato dal gran numero di pretendenti, che decise di istituire un concorso per stabilire chi era più qualificato a sposare la figlia. Nel turno di qualificazione, agli aspiranti veniva mostrato un disegno di due urne, ciascuna con tre maniglie numerate 1, 2, e 3 da cima a fondo. Gli veniva quindi richiesto di unire 1 con 1, 2 con 2, e 3 con 3 utilizzando curve che non si intersecano tra loro o che attraversano le urne. Questo compito non era così difficile, ma figlia di un califfo non può essere vinta così facilmente. Il padre, quindi, ha insistito affinché ogni corteggiatore che ha superato il primo turno debba competere anche in una finale. Anche questa volta venivano disegnate le stesse urne, ma i numeri sulle maniglie della seconda urna erano in ordine inverso⁽³⁾.

In questo caso il problema della figlia del califfo (o almeno la parte relativa alle finali) risulta equivalente al problema dei servizi, anche nella soluzione, visto che si narra in giro che la figlia del califfo morì zitella. Infatti, pur nella sua apparente semplicità, il rompicapo risulta irrisolvibile. Infatti se si collegano due case con tutti e tre i servizi, si arriva a constatare quasi con un certo imbarazzo che la stessa cosa non la si può fare con la terza casa. A meno di non... barare, proprio come fece Dudeney⁽³⁾:

Carnevale della Chimica #29

Provate a pensare a un rompicapo di questo genere: avete due bicchieri, uno riempito con 50 cucchiai di brandy e un altro con 50 cucchiai di acqua. A questo punto si prende un cucchiaio di brandy dal primo bicchiere e lo si versa all'interno del secondo. Si mescola e quindi si prende un cucchiaio da questa seconda mistura e lo si versa nel bicchiere di brandy. Fatto questo, provate a rispondere alla domanda: è maggiore la quantità di brandy trasferita dal primo bicchiere al secondo o la quantità di acqua trasferita dal secondo bicchiere al primo?
Rispondere correttamente può fornirvi, per esempio, un'utile chiave per comprendere un concetto di base per la chimica come la concentrazione, ma fate attenzione: un modo corretto per giungere alla risposta passa per la matematica!
La matematica, però, può essere utilizzata nella chimica anche in modi differenti, ad esempio utilizzando il concetto di simmetria: si possono infatti classificare i cristalli attraverso le loro simmetrie, siano esse assiali o puntuali. Oppure si potrebbe utilizzare il DNA per costruire dei solidi platonici: è molto interessante, infatti, notare come nella nanocostruzione di alcune particolari strutture chimiche, le molecole sembrano mostrare una maggiore stabilità quando si utilizzano come intelaiature proprio i solidi platonici:

Da Bhatia D., Mehtab S., Krishnan R., Indi S., Basu A. & Krishnan Y. (2009). Icosahedral DNA Nanocapsules by Modular Assembly, Angewandte Chemie International Edition, 48 (23) 4134-4137. DOI: 10.1002/anie.200806000 (pdf)

Inoltre i solidi platonici permettono il massimo volume di incapsulamento.
La tecnica in cui questo tipo di struttura viene utilizzata è l'assemblaggio modulare. Uno dei vantaggi della tecnica è che:

capsule chiuse stechiometricamente ben definite possono essere costruite con resa elevata anche ad alte concentrazioni come conseguenza della formazione di moduli intermedi precostituiti, oltre che un aumento della cooperazione associata con un ordine di assemblaggio progressivamente più elevato.

L'assemblaggio modulare può essere utilizzato anche per migliorare l'assemblaggio virale, poiché permette la costruzione di icosaedri sempre più complessi, e questo, aggiungo io, con un miglioramento nello studio dei virus e delle loro cure.
D'altra parte si può anche giocare con i solidi platonici e osservare che, probabilmente grazie alla loro capacità di essere associati con la spirale di Fibonacci, questi possono essere messi in una relazione visiva evidente con la struttura a doppia elica del DNA, struttura che, d'altra parte, può essere riprodotta utilizzando proprio la spirale di Fibonacci!

Palloncini, arte e matematica

Iniziamo a sperimentare l'abstract da inviare solo ai lettori del feed: in questa occasione vi proporrò la versione in italiano di un recente post (sottomesso al Carnival of Mathematics) in cui tre baldi ricercatori si dedicano alla descrizione di una teoria dei grafi associata con l'arte di modellare i palloncini!

Due palloncini con accanto i grafi corrispondenti

Ho scoperto da poco il sito vihart: è ricco di spunti interessanti e propone anche alcuni articoli particolari sulla matematica applicata in campi un po' inusuali, come ad esempio la costruzione di forme geometriche con i palloncini presentata in Computational Balloon Twisting: The Theory of Balloon Polyhedra di Erik e Martin Demaine e Vi Hart, il titolare del sito di cui sopra.
Il lavoro, sostanzialmente, si basa sui modi possibili in cui si può modellare un palloncino. I tre ricercatori così motivano il loro lavoro:

Modellare i palloncini è divertente: l'attività può sia intrattenere sia impegnare i bambini di tutte le età. Le torsioni dei palloncini possono essere un veicolo per insegnare concetti matematici legati ai palloncini. Come vedremo, questi concetti comprendono la teoria dei grafi, gli algoritmi sui grafi, i percorsi di Eulero, il percorso del postino cinese, i poliedri (3D e 4D), i colori, le simmetrie, e anche la completezza-NP. Anche i soli modelli sono utili per l'insegnamento, ad esempio nell'illustrazione delle molecole in chimica.

Ulteriore motivazione è la costruzione di strutture architettoniche con travi aeree (Army blows up building, Center manages technology of inflatable composite structures).

Il nostro approccio suggerisce che un lungo tubo a bassa pressione consente la costruzione temporanea di rifugi gonfiabili, cupole e altre strutture poliedriche, che possono essere più tardi riconfigurate in forme differenti e riutilizzate in vari luoghi. Rispetto al lavoro precedente, che disegna una struttura gonfiabile differente specificamente per ogni struttura desiderata, mostriamo la versatilità di un unico tubo.

Torsione di palloncini

La pratica della torsione la vedremo più sotto. Ora, seguendo i ricercatori nel loro articolo realizzato per i Proceedings of the 20th Canadian Conference on Computational Geometry (gli atti del congresso tenutosi nel 2008 sulla geometria computazionale), diamo un po' di definizioni, partendo da una definizione sintetica di palloncino che dal balloon originale passa a un sintetico bloon. In questo caso mi permetto di passare dal nostrano palloncino a un sintetico p-lone. Detto ciò, vediamo le definizioni:

(...) un p-lone è un segmento (una linea) che può essere torto in vari punti arbitrari per formare dei vertici in cui il p-lone può essere ripiegato come una cerniera. I punti finali di un p-lone sono anch'essi dei vertici. Due vertici possono essere legati per formare dei punti di connessione permanenti. Un p-lone ritorto è stabile se ogni vertice è o legato a un altro vertice o tenuto ad un angolo di curvatura non-nullo.

Si possono poi definire due modelli:

1. La torsione semplice: ogni sottosegmento di un p-lone tra due vertici forma un arco nel grafo associato, che rappresenta una porzione gonfiata di un palloncino.
2. Torsione pop: alcuni sotto segmenti di un p-lone tra due vertici possono essere segnate come sgonfie, non comparendo, così, nel grafo associato. Tali segmenti sgonfi possono essere ottenuti nei palloncini fisici modificando la pressione all'interno di un segmento gonfio subito accanto a quello sgonfio⁽¹⁾.