Il Teorema dei quattro colori

Il mondo doveva essere colorato.

Tutto ebbe inizio con la forgiatura della tavolozza dei Grandi Colori.

Il Verde fu dato agli elfi, gli esseri immortali più brillanti e leali di tutti.

Il Giallo ai re dei nani, grandi minatori e costruttori di città monocromatiche.

E il Blu, il Blu fu dato agli uomini, che più di tutti desiderano il mondo variopinto.

Ma tutti loro furono ingannati, perché venne creato un altro Colore.

Nella terra di Cromor, tra le fiamme del Monte Pigmento, Coloron, l’Oscuro Signore, generò in segreto un colore sovrano, capace di attirare lo sguardo di ogni osservatore: un Rosso per domarli tutti.

Uno a uno, i paesi liberi della Terra di Grigio caddero sotto il potere di Coloron, avvelenando la mente di tutti quanti con un annoso problema:

È possibile colorare ogni possibile mappa con solo quattro colori, in modo che assegnando a ogni territorio un colore questo non sia adiacente a uno del suo stesso colore?

Per secoli i paesi liberi della Terra di Grigio non riuscirono a trovare soluzione, restando in balia dell’Oscuro Signore.

Ma accadde qualcosa che egli non aveva previsto. Il problema venne risolto dall’essere più improbabile che si sarebbe mai aspettato…

Regole di ingaggio

Per ogni problema, per ogni domanda di natura matematica il primo passo è sempre quello di darne una descrizione precisa.

In questo modo si evitano zone d’ombra in cui è possibile dare diverse interpretazioni del problema.

Per prima cosa è opportuno definire il significato di “adiacente”.
Due territori su una mappa li definiremo “adiacenti” se hanno almeno una linea di confine in comune.

Si potrebbe obiettare che due territori sono adiacenti se i loro confini hanno almeno un punto in comune.

Questa sarebbe sicuramente una definizione valida, anche se diversa dalla nostra.
Per gli scopi di Coloron e della Terra di Grigio però non è molto interessante: ad esempio in una mappa fatta come una torta, ogni territorio-fetta sarebbe adiacente a tutti gli altri, toccandosi al centro.

In questo modo però, non basterebbero tutti i colori del mondo per evitare adiacenze.
Basterebbe prendere una mappa-torta con un numero di fette maggiore del numero di colori disponibili.

Un’altra cosa su cui è opportuno essere chiari è sul tipo di mappe ammissibili.

In questo caso vogliamo che siano mappe piane (ovvero “disegnabili su un foglio di carta”).
Inoltre vogliamo che ogni territorio sia connesso, ovvero composto da un solo pezzo (vogliamo evitare enclavi ed exclavi).

Astrazione

Una volta che le regole di ingaggio sono state condivise, è necessario trovare il campo di battaglia in cui affrontare la questione.

Un campo favorevole per gli abitanti della Terra di Grigio potrebbe essere quello della teoria dei grafi (di cui abbiamo parlato anche nell’articolo sui ponti di Königsberg).

Un grafo è un oggetto costituito da dei puntini (chiamati vertici) collegati tra loro attraverso delle linee (chiamate archi), in modo da ridurre all’osso le proprietà davvero importanti di un problema di natura topologica, come da Figura 2.

Un grafo planare
Figura 2: Un grafo (planare); i vertici sono i pallini colorati, gli archi le linee che li collegano. © Missione Scienza

Noi siamo interessati a quei tipi di grafi che prendono il nome di planari, ovvero quei grafi in cui gli archi non si intersecano mai tra di loro. Il grafo in Figura 2 per esempio è planare.

Una volta che il campo di battaglia è deciso opportunamente, le regole di ingaggio assumono una descrizione più naturale e possiamo dare una formulazione del problema scevra da possibili interpretazioni personali:

I vertici di ciascun grafo planare possono essere colorati utilizzando al massimo quattro colori, in modo tale che due vertici collegati da un arco non ricevano mai lo stesso colore?

La battaglia ora è pronta per entrare nel vivo!

Ma come la possiamo affrontare?

Di base, abbiamo due strategie di risoluzione, a seconda dell’effettiva risposta al problema.

Se non è possibile colorare i vertici del grafo in maniera opportuna, ci basta esibire una sola mappa-grafo e mostrare che ogni possibile strategia di colorazione ci conduce ad avere due vertici adiacenti dello stesso colore.

Se invece è possibile colorare i vertici del grafo in maniera opportuna, dobbiamo ingegnarci per mostrare che tutte, ma proprio tutte, le possibili mappe-grafo possono essere colorate.

Basandovi soltanto sul vostro fiuto matematico-guerresco, quale delle due strategie vi ispira più fiducia non potendo sapere la soluzione a priori?

Le prime ere

Il problema di colorare qualsiasi mappa utilizzando solo quattro colori venne formulato dal giovanissimo Francis Guthrie, nell’11.852 EU (1852 d.C.).

Il giovane botanico e matematico sudafricano notò che per colorare una mappa di contee britanniche bastava usare quattro colori in guisa tale che nessuna coppia di contee adiacenti si sarebbe ritrovata con lo stesso colore.

Da questa osservazione arrivò a congetturare che questo fosse possibile in generale, per ogni mappa.

Quello che all’apparenza può sembrare un piccolo indovinello si rivelò una congettura incredibilmente difficile, tanto da attirare molti eminenti matematici.

Nell’11.879 EU (1879 d.C.), il matematico britannico Alfred Kempe annunciò di aver trovato la dimostrazione della congettura dei quattro colori.
Grazie al suo manoscritto, tutti avrebbero potuto avere la certezza matematica che quattro colori sarebbero veramente bastati.

Ma, ahimè, il cuore dei matematici si corrompe facilmente [Nella finzione letteraria dell’articolo, non fraintendete] e i Colori del Potere hanno una volontà tutta loro!

La dimostrazione resse per undici anni, ma purtroppo nell’11.890 EU (1890 d.C.) Percy Heawood scoprì un errore fatale che comprometteva la dimostrazione di Kempe.

Per quasi cento anni il mondo non ebbe la luce della conoscenza sulla congettura dei quattro colori, dove tutte le dimostrazioni degli uomini sembravano non avere potere.

Il teorema dei quattro colori

Nell’11.977 EU (1977 d.C.), avvenne qualcosa che Coloron non aveva previsto.

Due matematici dell’Università dell’Illinois, Kenneth Appel e Wolfgang Haken, elaborarono un complesso algoritmo informatico in grado di dare la certezza matematica che quattro colori fossero sempre sufficienti.

Di tutte le possibili combinazioni di mappe possibili, si ridussero a studiare 1956 configurazioni fondamentali (poi ridotte a 1476), le cui proprietà topologiche esaurivano la totalità dei casi.

 

L’algoritmo poi, aveva il compito verificare una a una tutte le configurazioni.

Grande fu lo scalpore che ne derivò. Per la prima volta una dimostrazione veniva affidata nelle mani di una macchina, con tutto lo scetticismo e le contestazioni dei puristi.

L’algoritmo non contiene errori e la dimostrazione è valida per la comunità scientifica.

A livello storico, ha rappresentato una rivoluzione incredibile del mondo matematico, aprendo nuovi incredibili scenari per il futuro.

Perché, chissà, forse arriverà il momento in cui i computer plasmeranno la fortuna del mondo matematico.

Fonti

[1]: Il teorema dei quattro colori – Wikipedia

[2]: Il Teorema dei Quattro Colori – Maddmaths! (pdf)

Lorenzo De Biase

Matematico, ricercatore e sbadato professionista. Non chiedetegli di fare i conti al ristorante, non è capace: vi ritroverete a dover pagare quantità immaginarie ed essere costretti a lavare i piatti per qualche settimana.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *