Nel numero di settembre ho provato a indicare una possibile parentela tra le costellazioni e le reti.
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.
La Storia
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.
Il problema
Come spiegato nell’articolo di settembre, 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 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.
Nessun lettore ha inviato una dimostrazione veramente rigorosa, anche se le soluzioni proposte da Paolo Palma (che grazie alla sua rapidità si è aggiudicato l’abbonamento semestrale) e da Giorgia Hofer contenevano dei buoni tentativi in questo senso. Anche Patricio Calderari e Giuseppe Ruggiero hanno fornito la soluzione esatta, ma senza azzardare una dimostrazione di unicità.
A tutti questi lettori vanno però i nostri più vivi complimenti per avere affrontato la sfida!
.
La soluzione
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 a destra).
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):
