Utente:SilsisScalaZarli/Teorema dei quattro colori

{{stub matematica}}

File:QuattroColoriMappaEsempio.png

Esempio di mappa a quattro colori

Teorema

Il teorema dei quattro colori afferma che è sempre possibile colorare una mappa facendo in modo che due regioni confinanti comune abbiano un colore distinto e utilizzando solamente quattro colori.

In altre parole, se si prende una cartina politica, bastano quattro colori per colorare tutti gli stati senza che due stati confinanti abbiano lo stesso colore, se valgono le seguenti ipotesi:

• Si intenda per stati confinanti due stati che abbiano una striscia di confine in comune, non solo un numero finito di punti isolati: altrimenti una figura a forma di torta a fette sarebbe un controesempio.

• Ciascuno stato occupi un territorio connesso, cioè non abbia due regioni sconnesse che debbano avere lo stesso colore.

È immediato trovare mappe per le quali tre soli colori non sono sufficienti. Non è eccessivamente difficile dimostrare che ne bastano al più cinque (v. teorema dei cinque colori). Scendere a quattro ha comportato per la prima volta in matematica l'estensivo ricorso al computer.

Storia

Il problema venne presentato per la prima volta nel 1852, quando Francis Guthrie, uno studente di Augustus De Morgan, si accorse che per colorare una mappa della Gran Bretagna quattro colori erano sufficienti. Il primo riferimento a stampa si deve a Arthur Cayley, con l'articolo "On the colourings of maps", Proc. Royal Geog. Soc. 1 (1879), p. 259-261.

Ci furono vari tentativi di dimostrare il teorema, e due "dimostrazioni", una di Alfred Kempe nel 1879 e l'altra di Peter Tait nel 1880, che non furono trovate errate se non rispettivamente nel 1890 e 1891. Percy Heawood, che nel 1890 mostrò come la dimostrazione di Kempe fosse errata, dimostrò che cinque colori erano però sufficienti.

La dimostrazione del teorema per quattro soli colori è stata ottenuta nel 1977 da parte di Ken Appel e Wolfgang Haken grazie all'utilizzo di un computer. Proprio il rivoluzionario utilizzo del computer per la dimostrazione, e non come ausilio, ha scatenato una discussione sull'affidabilità degli algoritmi, e addirittura se il teorema è stato veramente dimostrato oppure no. In pratica la "dimostrazione" è consistita nel mostrare come fosse sufficiente considerare un numero finito, anche se assai grande, di topologie, poiché una configurazione qualunque poteva essere sempre ridotta a una di esse mediante una serie di operazioni che modificavano le relative posizioni delle aree interessate, ma non le proprietà topologiche della mappa. Il programma, eseguito su due diverse macchine con due diversi algoritmi, verificava che per ciascuna di queste configurazioni esiste una colorazione che impiega quattro colori.

È proprio questa analisi di casi discreti per mezzo di un computer che fa sì che alcuni matematici non reputino valida la dimostrazione, perché non c'è la certezza che l'algoritmo sia implementato correttamente. La logica e la teoria dell'informazione ci dicono infatti che non è possibile dimostrare la correttezza di un algoritmo, ma è facilissimo dimostrarne la non correttezza, tramite una controprova. Ad ogni modo nell'algoritmo non è stato trovato alcun errore. Altre due dimostrazioni potenzialmente indipendenti sono state proposte nel 1996 e nel 1998. Una dimostrazione non ancora verificata di sole 12 pagine è stata proposta nel 2004.

Curiosità

Bisogna stare attenti a non confondere il teorema dei quattro colori con quello, molto più semplice da dimostrare, che afferma che non possono esserci cinque regioni planari ciascuna delle quali confini con tutte e quattro le altre. Il problema è che non è possibile dire in maniera semplice che a furia di essere obbligati a usare una certa colorazione per i vincoli passati non si arrivi alla fine a un punto morto.

Formulazione in teoria dei grafi

Il teorema ha la sua formulazione più semplice in teoria dei grafi. In questa formulazione i vertici di ciascun grafo planare possono essere colorati con più di quattro colori in modo tale che due vertici adiacenti non ricevono lo stesso colore. In breve, “ogni grafo planare è 4-colorabile”. In questo modo, ogni regione della mappa è vista come il vertice del grafo, e due vertici sono connessi da uno spigolo se solo se le due regioni hanno un bordo in comune.

Generalizzazione

È possibile inoltre considerare il problema della colorazione su una superficie piuttosto che su un piano. Il problema della sfera è equivalente a quella del piano. Per le superfici chiuse (orientate come il toro o non orientate come la striscia di Möbius) di genere positivo, il massimo numero di colori necessari dipende dalla caratteristica di Eulero $\,\chi \,$ della superficie, in accordo con la formula:

$\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor$

dove le parentesi più esterne stanno ad indicare la funzione parte intera. La sola eccezione alla formula è la Bottiglia di Klein, la quale ha caratteristica di Eulero 0 e richiede 6 colori. Questa era inizialmente nota come congettura di Heawood e, una volta dimostrata, nel 1968 da Gerard Ringel e J.T.W. Youngs, ha preso il nome di Teorema della mappa colorata.

Controesempi del mondo reale

Nel mondo reale il territorio di alcune nazioni, anche se si escludono le isole, costituisce un insieme non connesso: ne sono esempi l’Alaska come parte degli Stati Uniti e l'enclave di Kaliningrad per la Russia completamente circondata dalla Polonia e dalla Lituania. Se la scelta dello schema dei colori richiede che il territorio di una particolare nazione sia tutto dello stesso colore, quattro colori potrebbero non essere sufficienti. Concettualmente, un tale vincolo che permetta alla mappa di essere non planare, rende non più valido il teorema. Per esempio consideriamo una mappa semplificata:

In questa mappa, le due regioni indicate con A indicano la stessa nazione, e devono avere la stessa colorazione. Questa mappa necessita di cinque colori, dal momento che le due regioni A insieme sono contigue a quattro altre regioni, ciascuna delle quali è contigua a tutte le altre. Se A consiste in tre regioni, potrebbero essere necessari sei o più colori; è possibile costruire una mappe che richiedono un numero arbitrario di colori.

Voci correlate

• Teoria dei grafi
• Topologia

Collegamenti esterni

• History of the Four Color Theorem in MacTutor
• An Update on the Four-Color Theorem di Robin Thomas (PDF File da Notices of the American Mathematical Society, Volume 45, number 7 August 1998)
• The Four Color Theorem di Robin Thomas

Bibliografia

• Kenneth Appel, Wolfgang Haken, John Koch (1977): Every Planar map id Four Colorable, Illinois Journal of Mathematics, vol. 21 pp. 439-567
• Kenneth Appel, Wolfgang Haken: Solution of the Four Color Map Problem, Scientific American, vol. 237 n. 4 pp. 108-121
• Kenneth Appel, Wolfgang Haken (1989): Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society
• Saaty, Kainen: The Four Color Problem: Assaults and Conquest ISBN 0-486-65092-8

[[Categoria:Teoremi]] [[Categoria:Teoria dei grafi]] [[Categoria:Topologia]]