Colorare le tessere del piano: quattro colori | Tangente

Sotto un’apparenza giocosa, se non addirittura infantile, le questioni di colorazione del piano pongono in realtà sfide temibili ai matematici e agli informatici. È infatti stato necessario attendere più di cento anni prima di poter affermare che ogni carta piana suddivisa in regioni connesse può essere colorata con quattro colori, in modo che due regioni confinanti ricevano sempre colori diversi. È il celebre teorema dei quattro colori, proposto già nel 1852 e la cui dimostrazione, nel 1976, da parte di Kenneth Appel e Wolfgang Haken richiedeva un pesante ricorso all’informatica e non era quindi unanimemente accettata. Una nuova dimostrazione, questa volta formale (ma ancora fondata in modo cruciale sull’uso del computer), fu pubblicata nel 2005 da Georges Gonthier e Benjamin Werner; oggi questa dimostrazione è assai più accettata dalla comunità. Ma se quattro colori bastano, non sono affatto necessari… Alcune carte potranno dunque essere colorate con tre colori, o persino con soli due.

Fare matematica infilando perle --------------------------------

Due colori possono bastare per realizzare una collana aperta, senza che due perle dello stesso colore siano a contatto. Basta alternare i colori… Ora chiudiamo su se stesso questo segmento di perle colorate. Per rispettare il vincolo, il colore all’inizio del segmento della collana deve essere diverso da quello alla fine. Il numero di perle utilizzate deve quindi necessariamente essere pari. Se la collana contiene un numero dispari di perle, diventa necessario disporre di un terzo colore…

Torniamo ora a una carta disegnata nel piano, o a una tassellazione. Come in una vetrata, due regioni si considerano adiacenti se hanno un confine comune, cioè una linea che non si riduce a un punto.

Si distinguono essenzialmente le tassellazioni regolari, composte da celle identiche o isometriche (quadrilateri, esagoni…), e le tassellazioni irregolari, composte da celle non isometriche, talvolta inoltre con lacune (assenze di contatto). Per colorare le tassellazioni regolari bastano tre colori, talvolta due. Così, per colorare una tassellazione esagonale regolare «a nido d’ape», basta disporre alternativamente serie di segmenti lungo «linee» ordinate colorate di blu, verde e rosso. Questa tassellazione non può essere modificata senza creare irregolarità, diversamente da quella del piano tassellato con quadrilateri.

Isoliamo in questa tassellazione un gruppo di celle strutturato attorno a un elemento centrale, il perno, circondato da una corona (ritroviamo qui la nostra collana iniziale) composta da un numero pari di celle, numerate da 1 a 6 e alternativamente verdi e blu. Questo gruppo dimostra che tre colori sono effettivamente necessari.

A esse si associa naturalmente un grafo.

La rappresentazione di una tassellazione mediante un grafo ha il vantaggio di mostrare le relazioni di adiacenza tra le celle senza preoccuparsi della loro geometria. Ogni vertice del grafo corrisponde a una cella, con il suo colore, e ogni lato materializza un confine della tassellazione. Questa rappresentazione garantisce che le proprietà del raggruppamento precedente, perno e corona, si applichino all’intera tassellazione regolare. La sovrapposizione del raggruppamento considerato con tutti gli altri perni della tassellazione mostra infatti che i colori delle corone sono corrispondenti: le caratteristiche locali del raggruppamento comprendente le tessere numerate da 0 a 6 si estendono all’intero piano.

Nella tassellazione iniziale, tutti i perni sono colorati di rosso. Le celle verdi e blu formano le corone, occupano le stesse posizioni sul quadrante di un orologio e partecipano ai raggruppamenti adiacenti.

-

Diciamolo con i quadrilateri -------------------------------

Come per la struttura a nido d’ape, si può costruire una tassellazione regolare del piano con quadrilateri: basta sovrapporre alternativamente successioni di segmenti lungo «linee» ordinate colorate di blu, verde e rosso, capovolgendole o traslandole. Questa tassellazione può assumere due diverse organizzazioni.

Il primo caso è identico alla rete esagonale: una corona di sei tessere circonda il perno. Questa corona comprende sei celle, un numero pari, e fornisce in totale tre colori diversi. Nel secondo caso, per la colorazione sono necessari soltanto due colori. La corona è certamente composta da otto celle, numero anch’esso pari, ma qui il perno può ricevere un colore compatibile con i vincoli.

Quando gli elementi del piano non sono più isometrici, la regolarità della colorazione del piano viene compromessa. Per colorare il piano della figura qui sotto, basta scegliere un gruppo di celle con il suo perno. Per esempio, la corona attorno alla cella 0 contiene sette celle. Poiché il loro numero è dispari, per colorare questa prima selezione sarà necessario usare quattro colori. Diamo al perno 0 il colore rosso, poi il blu alle celle 1, 3 e 5, alternato con il verde per le celle 2, 4 e 6. Ma poiché le celle 7 e 1 sono adiacenti, per completare la colorazione di questo gruppo occorre aggiungere alla tavolozza un nuovo colore, il giallo.

Per proseguire la colorazione, selezioniamo celle adiacenti al primo gruppo. Per esempio, scegliamo la cella 1, in blu, come perno del nuovo raggruppamento. Le celle che appartengono alla nuova corona sono quelle numerate 2, 0 e 7. Per completare la corona, basta prendere le tre celle successive, ciascuna a contatto con il nuovo perno blu: 11, 12, 13 e 8, da colorare in rosso. Questa corona, ora completa, contiene un numero dispari di celle; prenderà in prestito un colore, il giallo, dal raggruppamento precedente.

E se la carta presenta dei «buchi», cioè regioni lacunose? L’assenza di una cella in una tassellazione irregolare è simile al caso della tassellazione a due colori. La corona prosegue al di là del contatto mancante. Questa lacuna è rappresentata nello schema precedente dalla cella 8, non colorata. Il grafo seguente ne mostra le conseguenze.

-

Una lacuna nella tassellazione -------------------------

Se la cella 8 non esiste, allora c’è una lacuna attorno al perno 2. La corona è quindi composta dalle celle 1, 13, 9, 10, 15, 3 e 0.

Se invece la cella 8 è presente, la corona evita la cella 13 e si ricongiunge passando per 1, 8 e 9. La cella 8 sarà rossa per mantenere una tavolozza di colori minimale. Il teorema dei quattro colori ci garantisce comunque che una simile colorazione è possibile…