In cosa consiste il teorema matematico dei quattro colori?

In cosa consiste il teorema matematico dei quattro colori?
INFORMAZIONI SCHEDA
di

Il problema dei quattro colori è un teorema matematico originariamente enunciato nel 1852 da uno studente di nome Francis Guthrie, che aveva compreso la necessità di solo quattro colori per colorare una mappa delle contee britanniche.

Il teorema afferma che qualunque carta geografica possa essere colorata facendo uso di solo quattro colori, in maniera tale che due regioni adiacenti non abbiamo lo stesso colore. Va tuttavia precisato che bisogna porre in esame esclusivamente regioni connesse, e che abbiano un bordo in comune piuttosto che uno o più punti isolati. Su questa base, durante il XIX secolo furono fatti diversi tentativi per trovare una soluzione alla congettura, ma nessuna ricevette il favore della comunità scientifica. Per diventare teorema, la congettura dei quattro colori dovette aspettare l’avvento dei computer, che permise il trattamento di ingenti quantità di dati in tempi ragionevoli.

A tal proposito, il teorema fu dimostrato grazie all’informatica; per merito di due matematici dell’Università dell’Illinois, Kenneth Appel and Wolfgang Haken, che nel 1976 arrivarono alla soluzione del problema. La dimostrazione dei due matematici si basava sulla possibilità di provare che il numero infinito di mappe possibili può essere ridotto a un particolare insieme di 1936 configurazioni (più tardi ridotte a 1476), ciascuna delle quali non può essere parte di un controesempio del teorema. Questo insieme, chiamato “insieme inevitabile”, è un agglomerato di configurazioni tale che una qualsiasi mappa deve contenere almeno un elemento dell’insieme. Infatti, qualunque mappa, può essere ricondotta a un numero finito di topologie "notevoli" tramite operazioni che modificano le relative posizioni delle regioni che la costituiscono, ma non le proprietà topologiche della mappa stessa.

Il successivo “punto” teorico adottato da Appel e Haken fu l’applicazione del concetto di “configurazione riducibile”, cioè la possibilità di ridurre il numero delle regioni e dei colori necessari a colorare una configurazione di regioni, fino al numero di quattro. Per abbassare al minimo la possibilità di errore, il programma informatico fu eseguito su due distinti calcolatori con due algoritmi indipendenti; per completare l'analisi di tutte le possibili casistiche furono necessarie migliaia di ore di elaborazione. Il teorema dei quattro colori fu uno dei primi problemi ad avvalersi dell'utilizzo dell'informatica, scatenando diverse polemiche. Infatti, il fatto che la dimostrazione fosse impossibile da eseguire a “mano” portò molti matematici a dubitare della sua effettiva correttezza.

Quanto è interessante?
5