Per uscire da un labirinto, il mito ci invita a svolgere un gomitolo di filo come quello che Arianna, a Cnosso, dà al prode Teseo che si appronta a sfidare il Minotauro. Ma, a un immaginario Teseo-matematico, il filo di Arianna non serve solo per ritrovare la via del ritorno, è anche uno strumento per orientarsi nel labirinto ed evitare percorsi già fatti senza successo.
Pieno di incroci, svolte e percorsi ingannatori, il labirinto si presenta in ogni punto allo stesso modo pur essendo sempre disuguale, con strade ugualmente percorribili ma dall’effetto inaspettato al termine del tragitto. Per questo è un oggetto che risveglia l’interesse dei matematici. Ci parla di conoscenza da acquisire quando si penetra nell’essenza dei problemi, nei meandri della ricerca, ci raccomanda la necessità di disporre di un guida, un’opportuna Arianna-maestro.
La conoscenza richiede spesso di addentrarsi in complicate strutture del pensiero e l’immagine del labirinto descrive bene il carattere delle scelte che occorre compiere nella ricerca. In letteratura sono state proposte versioni del labirinto sotto la forma di un castello nelle cui stanze è facile perdersi, di una smisurata biblioteca, di un giardino segreto, di un codice irresolubile etc.
In matematica, non solo di miti si nutrono i problemi dei labirinti. Qui, la contraddizione fondamentale è fra chi lo percorre dall’interno – il viaggiatore – e chi lo vede dall’alto nel suo complesso, l’architetto. Fra lo studio “intrinseco”, che non oltrepassa i limiti naturali di una struttura, e l’attenzione anche all’ambiente esterno in cui la struttura prende vita. Fra le proprietà di carattere locale, che valgono in un “intorno”, e le proprietà globali, che si estendono all’intero sistema sotto esame.
Distinzioni che, in tempi recenti, hanno senso anche nello studio dei sistemi complessi, di strutture relative a fenomeni naturali e comportamenti umani, ma di cui si trovano facilmente precursori. Nella geometria delle superfici di Gauss e nelle varietà di Riemann e, già prima, ad esempio nel famoso problema di Eulero sui “ponti di Königsberg”, all’origine sia della teoria dei grafi e sia della topologia. Sono di carattere labirintico anche i problemi relativi alla mossa del cavallo nel gioco degli scacchi, affrontati oggi con l’uso del calcolo automatico ma a suo tempo con metodi empirici dallo stesso Eulero. Ad esempio, è possibile che il cavallo, con la sua tipica mossa, percorra interamente la scacchiera, partendo da una casella arbitraria e passando una e una sola volta per ogni altra casella? Un cammino hamiltoniano, nei termini dei cultori di teoria dei grafi.
Per questo problema, sono state elaborate numerose regole pratiche da eseguire a computer. Ad esempio, spostare ogni volta il cavallo in una casella da cui si diparte il minor numero di mosse ulteriori, oppure spedire il cavallo nella casella che ha la maggiore distanza dal centro della scacchiera. Insomma, impegnare il minor numero di caselle oppure girare alla larga e accentrarsi solo se non ci sono alternative.
Riuscirà il cavallo a uscire dal labirinto, cioè risolvere il problema? Il Teseo-matematico, per risolvere il proprio labirinto, ha bisogno di una regola algoritmica più che di suggestioni empiriche. Ma esiste una tale regola? Si dice ad esempio, che basta sempre tenere la destra, o la sinistra, per uscire da un labirinto disposto su un piano. Ma se esistessero dei “buchi”, intorno ai quali l’algoritmo ti fa girare indefinitamente? Se – come si dice – il labirinto, in quanto grafo planare, non fosse “semplicemente connesso”? Si rischia di girare in tondo. Il viaggiatore nel labirinto si accorge di questo pericolo quando, percorrendo un corridoio per la prima volta giunge a un incrocio già visitato: significa che quel corridoio chiude un ciclo. Tornare indietro subito e darsi da fare diversamente.
Sono i cicli che complicano la ricerca della strada. Se il labirinto-grafo fosse organizzato ad “albero” – un ingresso che ne costituisce la radice e percorsi che portano in ogni caso a vicoli ciechi – basterebbe percorrere tutti i corridoi due volte, una in andata l’altra in ritorno, per uscirne dallo stesso punto in cui si è entrati. Ma, più spesso questo non accade e il viaggiatore deve applicare la strategia di eliminarli fittiziamente, riconoscendo i cicli e riuscendo a trattarli come fossero vicoli ciechi. Il viaggiatore riesce così, come fanno spesso e saggiamente i matematici, a ridursi al problema precedente, quello del labirinto come albero.
Per quanto sembri strano, le prime pubblicazioni relative ad algoritmi locali – quindi disponibili al viaggiatore, che in ogni istante ha la percezione solo del corridoio in cui si trova e dei segni che ha eventualmente lasciato in precedenti passaggi – risalgono alla seconda metà dell’Ottocento. In esse si trovano dimostrazioni complete e convincenti. La loro differenza consiste nella praticità d’uso e nell’economia, nel senso di riuscire a risolvere il labirinto, come si dice, con il minor numero di passaggi per i corridoi. A questo proposito è ottimale l’algoritmo proposto da Gaston Tarry nel 1895: arrivati ad un incrocio, indipendentemente dal fatto che si sia già passati da lì, procedere in un corridoio non ancora percorso nella direzione in cui si sta imboccando. Se questo non è possibile si dovrà tornare indietro ma, ecco la regola fondamentale, non ritirarsi lungo il corridoi da cui si è pervenuti la prima volta a quell’incrocio, a meno che questa sia l’unica possibilità: lungo il “corridoio di scoperta” di quell’incrocio ci si ritira come ultima ratio.
Tutto bene. Il viaggiatore-matematico-Teseo ha la sua regola ottimale. A meno che non incontri il re degli arabi di un racconto di Borges che lo porta nel più inestricabile dei labirinti, il deserto, “che non ha scale da salire, né porte da forzare, né faticosi corridoi da percorrere, né muri che ti vietano il passo”.
Renato Betti
Sintesi di Renato Betti, Il filo di Arianna. Nuova lettera Matematica n.7 nuova Serie pp.62-76.
Scarica l’articolo completo apparso sulla rivista Nuova Lettera Matematica.