Il teorema dei quattro colori spiegato

Nel 1852 un giovane matematico, mentre colorava una mappa delle contee d'Inghilterra, notò che quattro colori sembravano bastare per distinguere le contee vicine. Poteva essere vero per ogni mappa possibile? La domanda divenne uno dei problemi più famosi della matematica, attirò una celebre dimostrazione sbagliata che resistette per undici anni e fu infine risolta nel 1976 in un modo che cambiò ciò che i matematici accettano come dimostrazione.

Una mappa di paesi irregolari colorata con quattro colori in modo che nessuna coppia di vicini abbia lo stesso colore
Una mappa di paesi irregolari colorata con quattro colori in modo che nessuna coppia di vicini abbia lo stesso colore

La domanda

Francis Guthrie, ex studente di Augustus De Morgan, si chiese se qualsiasi mappa possa essere colorata con quattro colori in modo che i paesi con un confine in comune ricevano colori diversi. Due regole rendono precisa la domanda. I paesi devono essere connessi, ciascuno in un unico pezzo, e i paesi che si incontrano in un solo punto non contano come vicini. Tre colori chiaramente non bastano sempre, poiché un paese circondato da un anello di altri tre che si toccano tutti ne richiede un quarto. La domanda è se serva mai un quinto.

Le mappe come grafi

Segna un punto in ogni paese e traccia una linea tra due punti ogni volta che i loro paesi hanno un confine in comune. Il risultato è un grafo e, poiché la mappa giace su un foglio piano, le linee si possono tracciare senza incroci: il grafo è planare. Colorare la mappa significa colorare i vertici di questo grafo in modo che gli estremi di ogni spigolo siano diversi. Il numero minimo di colori che funziona è il numero cromatico, e il teorema dei quattro colori afferma che nessun grafo planare ha numero cromatico superiore a quattro.

La dimostrazione fallita di Kempe

Nel 1879 l'avvocato e matematico Alfred Kempe pubblicò una dimostrazione. La sua idea ingegnosa, oggi chiamata catene di Kempe, consiste nello scambiare due colori lungo una catena connessa di paesi per liberare un colore dove serve. La dimostrazione fu accettata per undici anni, finché nel 1890 Percy Heawood vi trovò una lacuna. La correzione di Heawood dimostrò un risultato più debole: cinque colori bastano sempre. Le catene di Kempe sopravvissero e divennero uno strumento della dimostrazione definitiva.

Perché cinque è facile

Ogni grafo planare ha un vertice con al massimo cinque vicini; ciò discende dalla formula di Eulero, che limita un grafo planare con n vertici ad al massimo 3n − 6 spigoli. Togli un vertice del genere, colora il resto della mappa con lo stesso ragionamento e rimetti il vertice. Se i suoi vicini usano meno di cinque colori, uno è libero. Se li usano tutti e cinque, uno scambio lungo una catena di Kempe ne libera sempre uno. Con quattro colori lo stesso scambio può fallire, ed è proprio la lacuna che sfuggì a Kempe.

La dimostrazione al computer

Nel 1976 Kenneth Appel e Wolfgang Haken, all'Università dell'Illinois, dimostrarono il teorema. Mostrarono che ogni mappa contiene almeno una di 1.936 configurazioni appartenenti a un insieme inevitabile e che ogni configurazione è riducibile: una mappa minima che richiedesse cinque colori non potrebbe contenerla. Verificare la riducibilità richiese più di mille ore di calcolo al computer, troppo per un controllo a mano. Molti matematici erano a disagio con una dimostrazione che nessuna persona poteva leggere per intero, e iniziò il dibattito sulle dimostrazioni assistite dal computer.

Wolfgang Haken, che con Kenneth Appel dimostrò il teorema dei quattro colori all’Università dell’Illinois nel 1976.
Wolfgang Haken, che con Kenneth Appel dimostrò il teorema dei quattro colori all’Università dell’Illinois nel 1976.

Dimostrazioni più semplici e verifica completa

Nel 1996 Neil Robertson, Daniel Sanders, Paul Seymour e Robin Thomas pubblicarono una dimostrazione più sistematica con 633 configurazioni, ancora verificata al computer ma più facile da controllare. Nel 2005 Georges Gonthier e Benjamin Werner formalizzarono l'intera dimostrazione nell'assistente di dimostrazione Coq, così che un piccolo programma affidabile verifica ogni passaggio logico. Oggi il teorema dei quattro colori è uno dei risultati della matematica verificati con più cura.

Algoritmi di colorazione

Trovare una colorazione con quattro colori di una data mappa è rapido nella pratica, ma trovare il numero minimo di colori per un grafo generico è difficile: decidere se bastano tre colori è NP-completo. Tra i metodi pratici ci sono la colorazione greedy in ordine di grado decrescente, DSATUR, che colora come prossimo il vertice più vincolato, e la ricerca con backtracking, che esplora le scelte e le annulla quando si blocca. La colorazione dei grafi serve a pianificare esami senza sovrapposizioni, ad assegnare frequenze radio in modo che trasmettitori vicini non interferiscano e ad allocare i registri nei compilatori.

Esplora

Apri la mappa da colorare dei quattro colori per generare mappe da 4 a 120 paesi, colorarle a mano con quattro colori e vedere i conflitti comparire in rosso. Lascia che la colorazione greedy, DSATUR o il backtracking risolvano la mappa passo dopo passo, mostra il grafo dei paesi confinanti e verifica il numero minimo di colori di cui la mappa ha davvero bisogno.

Domande frequenti

Il teorema aiuta i cartografi?

Poco. Le mappe reali di solito sono colorate con più colori per chiarezza, e includono oceani, laghi e paesi in più parti, che il teorema non considera. La sua importanza è matematica: ha spinto lo sviluppo della teoria dei grafi e ha sollevato la questione di che cosa conti come dimostrazione.

Che cos'è una catena di Kempe?

Prendi due colori, per esempio rosso e blu, e un paese colorato di rosso. La sua catena di Kempe è l'insieme di tutti i paesi rossi e blu che puoi raggiungere da esso passando solo attraverso vicini rossi e blu. Scambiare rosso e blu in tutta la catena mantiene valida la colorazione e può liberare un colore per un paese accanto alla catena.

Perché i paesi in più parti fanno cadere il teorema?

Se un paese può essere formato da regioni separate che devono avere tutte lo stesso colore, il grafo dei vicini non è più planare, e si possono costruire mappe che richiedono qualsiasi numero di colori fino a 12 con due parti per paese, come studiò Heawood nel suo problema degli imperi.

Perché lo strumento crea le mappe a partire da punti?

Ogni paese è la regione del quadrato più vicina a un punto casuale che a qualsiasi altro, un diagramma di Voronoi. Si ottengono così mappe dall'aspetto realistico con paesi convessi, e due paesi sono vicini esattamente quando le loro regioni condividono un tratto di confine, cosa che l'app calcola con precisione.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri la mappa da colorare dei quattro colori