Don't take life too seriously: it's just a temporary situation

Il problema dei quattro colori consiste nel dimostrare che qualsiasi mappa disegnata sul piano o sulla sfera può essere colorata con 4 colori, in modo che non vi siano due regioni dello stesso colore con una parte di confine comune.

 

Si vede facilmente che quattro colori sono necessari, anche per la semplice mappa mostrata di seguito.

 

 

Mappa che richiede 4 colori

 

Ciascuna delle 4 regioni confina con tutte le altre, quindi 4 colori sono necessari.

Augustus De Morgan (Madurai, India, 27/6/1806 – Londra, 18/3/1871) dimostrò che sul piano non possono esistere 5 regioni, ciascuna delle quali a contatto con tutte le altre, ma questo non basta a dimostrare che 4 colori bastano, perché potrebbe esistere una mappa con molte regioni, che ne richiede 5. In effetti colorando mappe complicate capita spesso di ritrovarsi a colorare una regione che confina con altre, di 4 colori diversi. In tal caso, invece di usare un quinto colore, si può tornare indietro e colorare diversamente qualche regione, in modo da far bastare 4 colori. Il problema consiste nel dimostrare che questo è sempre possibile.

Sono opportune due precisazioni, senza le quali servirebbero infiniti colori:

  • le regioni considerate sono parti di superficie continue e compatte, delimitate da linee chiuse e non divise in parti separate;

  • due regioni sono confinanti se condividono un tratto del loro confine, non un singolo punto.

 

Il problema venne posto da Francis Gutrie nel 1852, ma acquistò notorietà solo il 13/6/1878, quando Arthur Caley chiese ai membri della London Mathematical Society di risolverlo, dichiarando di non essere riuscito nell’impresa.

 

Alfred Bray Kempe pubblicò nel 1879 una dimostrazione, semplice e ingegnosa, che convinse tutti, e che gli valse la nomina a Fellow della Royal Society.

Solo nel 1890 Percy John Heawood scoprì un sottile ma fatale errore nella dimostrazione di Kempe, passato sino a quel momento inosservato.

 

Il problema venne finalmente risolto, diventando il teorema dei 4 colori, nel 1976 da Kenneth Appel e Wolfgang Hachen con un monumentale lavoro: la dimostrazione è lunga 900 pagine.

 

Curiosamente il problema analogo di determinare il numero di colori necessari per mappe disegnate su superfici più complicate, come il toro e le ciambelle con n fori, era stato risolto vari anni prima (v. congettura di Heawood).

 

Sono anche state affrontate, e in gran parte risolte, varie generalizzazioni, come determinare il numero di colori necessari per mappe di imperi formati da varie regioni disgiunte o con una parte sulla Terra e una sulla Luna (v. numeri di Heawood).

Vedi anche

Numeri di Heawood.

Bibliografia

  • Appel, Kenneth;  Haken, Wolfgang;  "La soluzione del problema dei 4 colori" in Le Scienze, Milano, n. 113, gennaio 1978, pag. 54 – 65.
  • Coxeter, H.M.S.;  "The Mathematics of Map Coloring" in Mathematical Solitaires and Games, Baywood Publishing Co., di Benjamin L. Farmingdale, Schwartz, 1968.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 142, giugno 1980, pag. 108 – 111.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 5, gennaio 1969, pag. 91.
  • Gardner, Martin;  The Last Recreations, New York, Springer-Verlag, 1997.
  • Heawood, Percy John;  "Map Colour Theorems" in Quarterly Journal of Pure and Applied Mathematics, n. 24, pag. 332 – 338, 1890.
  • Stewart, Ian;  I grandi problemi della matematica, Torino, Einaudi, 2014 -

    trad. di The Great Mathematical Problems, Joat Enterprises, 2013

  • Wilson, Robin;  Four Colors Suffice, Princeton University Press, 2002 -

    Storia molto ben documentata del teorema dei 4 colori.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.