Gli enigmi di Coelum: alberi nel cielo

Come qualcuno ricorda, da ormai quasi due anni curo sulla prestigiosa rivista Coelum Astronomia una rubrica di matematica ricreativa, significativamente intitolata Moebius.

Questa mia attività è per me qualcosa di entusiasmante: immeritatamente posso dire di fare qualcosa di vagamente simile a quello che hanno fatto o fanno alcuni giganti della divulgazione matematica, come Martin Gardner, Douglas Hofstadter, e, per citare alcuni maestri di casa nostra, i Rudi Mathematici.

Insomma, lo ammetto: per me Moebius è un gran divertimento. Gli ingredienti principali di ogni articolo sono tre: un po' di matematica raccontata con semplicità, una sfida lanciata al lettore e un pizzico di astronomia per condire il tutto.

Se volete divertirvi anche voi con la matematica giocosa di Moebius, e mettervi alla prova ogni mese con un avvincente enigma, non dovete fare altro che abbonarvi a Coelum: vi basterà poi risolvere per primi il problema del mese per vincere sei mesi gratuiti!

Per gentile concessione della redazione, ho la facoltà di riproporre su questo blog, con qualche mese di ritardo, gli approfondimenti, a suo tempo usciti sul sito di Coelum, riguardanti i temi trattati negli articoli pubblicati sulla rivista cartacea: sono argomenti che in alcuni casi ho già in parte trattato su Mr. Palomar. Ma vedrete, non mancheranno le novità interessanti.

Comincerò con le note relative all'articolo uscito a settembre 2013, nel quale avevo suggerito una possibile parentela tra le costellazioni e le reti in matematica: in entrambi i casi ci troviamo di fronte a un insieme di nodi (le stelle) congiunte da archi (le linee che danno una "forma" alle costellazioni, così come vengono convenzionalmente raffigurate negli atlanti stellari).

I matematici hanno cominciato a parlare di reti, o di grafi, come talvolta si preferisce dire, in tempi relativamente recenti. Ad introdurre per primo questo concetto fu, intorno al 1736, lo svizzero Leonhard Euler (spesso italianizzato in Eulero), uno dei più grandi geni matematici di ogni epoca.

A offrire a Eulero l’assist per fondare la teoria dei grafi fu un curioso enigma che si ispirava alla particolare conformazione della città prussiana di Königsberg.

Questa città, che oggi si chiama Kaliningrad e si trova in territorio russo, è famosa per avere dato i natali al filosofo Immanuel Kant e al matematico David Hilbert. Il fiume che attraversa l’area cittadina, il Pregel, forma due vaste isole, che nel Settecento erano collegate tra di loro e con le due aree principali della città tramite sette ponti. Il problema consisteva nel tracciare un percorso che attraversasse ognuno dei sette ponti una e una sola volta, tornando infine al punto di partenza.
Oggi i matematici chiamano “euleriano” un percorso di questo tipo. Cosa fece Eulero per meritare un simile onore? Semplicemente dimostrò che a Königsberg non esiste un circuito euleriano.

Come vi riuscì? La mossa vincente fu formulare il problema in termini di “rete”. Eulero rappresentò infatti ciascuna delle aree urbane come un “nodo” e ciascuno dei ponti come un “arco”. Analizzando la rete che si era originata, si accorse che da ogni nodo usciva un numero dispari di archi; nel contempo riuscì a dimostrare che in una rete esiste un percorso euleriano se e soltanto se non vi sono nodi toccati da un numero dispari di archi. Ecco allora che la passeggiata euleriana sui ponti di Königsberg è impossibile.

Il bello è che Eulero fu il primo in assoluto a risolvere un problema ricorrendo a strumenti di questo tipo: mentre disegnava il grafo della città di Königsberg, di fatto Eulero stava fondando un nuovo importante ramo della matematica.
I colleghi di Eulero lo snobbarono per questa sua trovata: secondo loro soltanto argomenti come l’analisi infinitesimale, la teoria dei numeri e la geometria erano degni delle attenzioni di un matematico, e tutto il resto era solo perdita di tempo.
Ma proprio il tempo diede ragione a Eulero. Oggi la teoria dei grafi è considerata un’area fondamentale della matematica, insostituibile in molti rami della fisica, dell’ingegneria, dell’informatica.
Senza rendercene conto, tutti i giorni abbiamo a che fare con le reti: cosa sono, secondo voi, gli alberi genealogici, gli organigrammi aziendali, i diagrammi di flusso, gli schemi elettrici? E che dire del reticolo di strade della nostra città, della rete dei telefoni cellulari, di internet, del web, dei social network?
Perché, allora, non trattare anche le costellazioni come reti? Un tempo gli atlanti si limitavano a mostrare le posizioni delle stelle presenti in ogni costellazione, decorando il tutto con eleganti disegni ispirati a personaggi mitologici; ma in tempi più recenti sono comparse le familiari linee che congiungono le stelle tra di loro. Questi intrecci sono reti a tutti gli effetti, e per di più planari, in quanto le linee non si intersecano mai, se non nelle stelle stesse.

Già nel 1930 furono stabiliti i confini convenzionali delle costellazioni, ma il modo in cui le stelle di ogni costellazioni vengono collegate tra di loro non fu mai oggetto di standardizzazione. A seconda che il disegno di una costellazione contenga o meno circuiti chiusi, ci possiamo trovare di fronte a una rete qualsiasi o ad una rete speciale, chiamata “albero”.

Sono chiamati alberi, quindi, i grafi in cui, presi a caso due nodi, esiste esattamente un percorso che li congiunga. Ovviamente, il carattere “arboreo” o meno di una costellazione è legato alla libera scelta di come unire le stelle l’una all’altra. Cassiopea, ad esempio, viene tipicamente disegnata come una grande W, ma nessuno ci impedisce, per una volta, di trasgredire e tratteggiarla in modo diverso.
Il problema di settembre 2013 richiedeva appunto di ridisegnare Cassiopea in modo che le stelle Segin, Ruchbah e Tsih siano collegate ciascuna a una sola stella, mentre Caph è collegata a tre stelle. Veniva anche richiesto di dimostrare l’unicità della soluzione trovata.

Siete in grado di risolvere l'enigma? Se volete provarci da soli, aspettate a leggere il seguito di questo post! (ovviamente, per chi indovinerà la risposta non ci sarà nessun premio, se non la soddisfazione di essere riusciti nell'intento)

Un possibile approccio per risolvere il rompicapo è il seguente.

 

Dato che le stelle prese in considerazione sono cinque (Segin, Ruchbah, Tsih, Shedir e Caph), si tratta di disegnare un albero formato da cinque nodi. Ora, dal punto di vista della topologia della rete, un simile albero può essere di tre tipi soltanto (vedi figura).

Che esistano soltanto queste tre topologie lo si può vedere molto facilmente. Provate a costruire un albero di cinque nodi passo dopo passo, cioè partendo da un nodo soltanto e aggiungendo via via gli altri: vi accorgerete che le opzioni possibili vi porteranno comunque verso queste tre conformazioni, e nessun’altra è raggiungibile.
Dato che nella nuova Cassiopea che vogliamo costruire c’è una stella (Caph) collegata a tre stelle, possiamo senz’altro escludere il primo tipo di albero (in cui nessun nodo ha tre adiacenti) e anche il secondo (nel quale il nodo centrale ha quattro adiacenti, e gli altri quattro ne hanno soltanto uno, appunto quello centrale).
Siamo quindi nel terzo prototipo di grafo, nel quale vi è un nodo C (nel nostro caso Caph) legata a tre suoi vicini (B, D, E). Dato che Segin, Ruchbah e Tsih devono avere una sola vicina, il nodo B è sicuramente Shedir, adiacente a Caph e collegato a due nodi.
Per trovare la soluzione, non ci resta che abbinare i nodi A, D ed E alle stelle Segin, Ruchbah e Tsih. Due di questi (D ed E) devono legarsi a Caph, e un altro (A) a Shedir. Da una rapida analisi della disposizione delle stelle di Cassiopea, appare evidente che soltanto scegliendo Ruchbah come nodo A (e quindi abbinando Segin e Tsih ai nodi D ed E) si evitano sovrapposizioni di linee, preservando la planarità del grafo.
Quindi l’unica soluzione compatibile con gli indizi dati è quella illustrata nella figura seguente (dove gli archi dell’albero individuato sono mostrati in rosso, sovrapposti alla tradizionale W di Cassiopea):