Teorema dei quattro colori for dummies: cosa dice e a cosa serve

190 anni fa nasceva Francis Guthrie, un nome che non dice molto ai più ma che, in realtà, ha dato tantissimo alla scienza: fu lui infatti, per primo, a formulare la base di quello che sarebbe diventato il teorema dei quattro colori.

Tale teorema dei quattro colori afferma che:

“È possibile colorare qualsiasi mappa piana con un massimo di quattro colori, in modo tale che due regioni adiacenti non abbiano mai lo stesso colore.”

In altre parole, se hai una mappa divisa in regioni (come gli stati di un continente o le province di un paese), bastano al massimo quattro colori per colorarla, senza che due regioni confinanti abbiano lo stesso colore.

Un po’ di storia:

• Fu congetturato nel 1852 dal matematico Francis Guthrie.
• Per più di un secolo, vari matematici provarono a dimostrarlo senza successo.
• Fu dimostrato nel 1976 da Kenneth Appel e Wolfgang Haken con l’uso di un computer, segnando una delle prime dimostrazioni assistite da calcolo automatico.

È un teorema fondamentale nella teoria dei grafi e ha implicazioni in vari campi, dalla cartografia all’ottimizzazione delle reti.

Era il 1852, e Francis Guthrie, studente di matematica, si accorse che per colorare la mappa delle contee britanniche bastava usare al massimo quattro colori. Sembrava che fosse proprio cosà¬, ma non c’era stato modo di dimostrarlo formalmente, almeno all’epoca. Un problema che avrebbe afflitto per molti anni i matematici delle generazioni successive, per poi essere risolto negli anni Settanta grazie all’ausilio di un algoritmo informatizzato, realizzato dai matematici Kenneth Appel e Wolfgang Haken.

L’intuizione di Guthrie aprì un mondo: il metodo di dimostrazione di un teorema sulla base di un algoritmo non è mai stato accettato universalmente dalla comunità  scientifica, dato che era impraticabile effettuare una contro-verifica a livello manuale. Nonostante questo non risultano esserci errori nell’algorito, il che è anche una riprova classica che in informatica possono esistere soluzioni poco “eleganti” quanto efficaci, il che è anche alla base di molte delle tecnologie che usiamo nella quotidianità . Semmai, quindi, potremmo dire che l’informatica ha aperto a nuove possibilità  il mondo della matematica, quantomeno nell’ambito dei grafi e computazionale.

Ecco un po’ di esempi dell’applicazione del teorema dei quattro colori.

Applicazioni pratiche del teorema? Non sono ovvie, ma ci sono: poniamo di dover distribuire vari ripetitori Wi-Fi all’interno di un edificio, evitando la sovrapposizione tra frequenze per quelli adiacenti. Questo è vero se assumiamo un modello di distribuzione del Wi-Fi che, nella realtà , potrebbe rivelarsi poco pratico o irrealistico, ad esempio nel momento in cui ci siano più router o saponette Wi-Fi che devono per forza condividere la stessa frequenza: in questi caso le frequenze sono molte più di quattro , ovviamente. Il teorema dei quattro colori, pertanto, si applica su modelli basati su grafi planari non contigui (informalmente potremmo definirli “compatti”), ed è certamente vero in questo caso.

Ma su alcuni tipi di mappe, come quella della Terra con il mare incluso, i colori necessari sono cinque, in realtà…