Teorema dei quattro colori
Da Wikipedia, l'enciclopedia libera.
Il teorema dei quattro colori afferma che, data una superficie piana divisa in regioni connesse, come ad esempio una carta geografica politica, sono sufficienti quattro colori per colorare ogni regione facendo in modo che regioni adiacenti non abbiano lo stesso colore. Due regioni sono dette adiacenti se hanno almeno un segmento di confine in comune, non solo uno o più punti isolati (altrimenti una figura a forma di torta a fette sarebbe un controesempio). Ciascuna regione deve inoltre occupare un territorio connesso, cioè non deve essere formata da due o più parti sconnesse come lo sono, nella realtà, nazioni quali Stati Uniti d'America, Angola, o Russia.
È 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.
Indice |
[modifica] Storia
La congettura venne presentata per la prima volta nel 1852, quando Francis Guthrie, uno studente di Augustus De Morgan, si accorse che per colorare una mappa delle contee britanniche erano sufficienti quattro colori. La prima pubblicazione relativa all'argomento si deve ad Arthur Cayley, con l'articolo "On the colourings of maps", Proc. Royal Geog. Soc. 1 (1879), p. 259-261.
Negli anni successivi molti matematici tentarono invano di dimostrare il teorema. La prima, acclamata "dimostrazione", a lungo riconosciuta come definitiva, fu formulata nel 1879 da Alfred Kempe; nel 1880 Peter Tait annunciò di avere trovato una ulteriore dimostrazione del teorema. Nel 1890 Percy Heawood scoprì l'errore che minava la dimostrazione di Kempe, ben undici anni dopo la sua formulazione; l'anno successivo, ad opera di Julius Petersen, anche la dimostrazione di Tait fu riconosciuta errata. Confutando la dimostrazione di Kempe, Heawood dimostrò tuttavia che cinque colori erano sufficienti per qualsiasi mappa.
La definitiva dimostrazione del teorema per quattro soli colori è stata fornita nel 1977 da parte di Kenneth Appel e Wolfgang Haken, due matematici dell'Università dell'Illinois, grazie a un complesso algoritmo informatico.
La dimostrazione si basa sulla riduzione del numero infinito di mappe possibili a 1.936 configurazioni (poi ulteriormente ridotte a 1.476), per le quali la validità del teorema viene verificata caso per caso dal computer. Qualsiasi mappa può infatti essere ricondotta a un numero finito, sebbene assai elevato, di topologie "notevoli" tramite operazioni che modificano le relative posizioni delle regioni che la costituiscono, ma non le proprietà topologiche della mappa stessa.
Per ridurre al minimo la possibilità di errore, il programma fu eseguito su due diverse macchine con due algorimi indipendenti; per completare l'analisi di tutti i casi possibili fu necessario far lavorare i computer per migliaia di ore. Alla fine, servirono più di 500 pagine per trascrivere a mano tutte le verifiche che costituivano la dimostrazione.
Il rivoluzionario utilizzo di algoritmi informatici per verificare l'esattezza della congettura scatenò grandi polemiche sull'affidabilità di questi metodi. Il fatto che la dimostrazione fosse basata sull'analisi di una moltitudine di casi discreti portò alcuni matematici a contestarne l'effettiva validità: sia per l'impraticabilità di una verifica manuale di tutti i casi possibili, sia per l'impossibiltà di avere la certezza che l'algoritmo fosse implementato correttamente. La logica e la teoria dell'informazione ci dicono infatti che non è possibile dimostrare la correttezza di un algoritmo, ma tuttavia sono sufficienti semplici controprove per dimostrarne la non correttezza. Ad ogni modo, nonostante le accuse di scarsa "eleganza", nell'algoritmo non è mai stato trovato alcun errore.
Altre due dimostrazioni potenzialmente indipendenti sono state proposte nel 1996 e nel 1998, mentre una dimostrazione (non ancora verificata) di sole 12 pagine è stata proposta nel 2004.
[modifica] Curiosità
Bisogna stare attenti a non confondere il teorema dei quattro colori con quello, molto più semplice da dimostrare, che afferma che non possono esistere cinque regioni planari ciascuna delle quali confini con tutte e quattro le altre. La differenza sostanziale è costituita dall'impossibilità di esprimere in maniera semplice la procedura da seguire per i differenti vincoli, man mano che si procede nella colorazione.
[modifica] Formulazione in teoria dei grafi
Il teorema può essere espresso in forma più comprensibile sfruttando la teoria dei grafi. In questa formulazione i vertici di ciascun grafo planare possono essere colorati utilizzando al massimo quattro colori, in modo tale che due vertici adiacenti non ricevano mai lo stesso colore. In breve, si può affermare che "ogni grafo planare è 4-colorabile". Questa rappresentazione associa ogni regione della mappa a un vertice del grafo; due vertici sono connessi da uno spigolo se e solo se le due regioni corrispondenti hanno un segmento di bordo in comune.
[modifica] Generalizzazione
È inoltre possibile considerare il problema della colorazione su una superficie piuttosto che su un piano. Il problema applicato alla sfera è equivalente a quello sul piano. Per le superfici chiuse (orientate come il toro o non orientate come il nastro di Möbius) di genere positivo, il massimo numero di colori necessari dipende dalla caratteristica di Eulero 
della superficie, in accordo con la formula:
dove le parentesi più esterne stanno a indicare la funzione parte intera. Per esempio, il toro ha caratteristica di Eulero = 0 e p = 7: saranno pertanto necessari al massimo sette colori per colorare qualsiasi mappa su una superficie toroidale. Questa formula, inizialmente nota come congettura di Heawood, ha preso il nome di Teorema della mappa colorata dopo essere stata dimostrata da Gerard Ringel e J.T.W. Youngs nel 1968.
La sola eccezione alla formula è la Bottiglia di Klein, la quale ha caratteristica di Eulero uguale a 0 e richiede sei colori.
[modifica] Controesempi nel mondo reale
Nel mondo reale esistono nazioni il cui territorio, 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, appartenente alla Russia ma completamente circondata dalla Polonia e dalla Lituania. In casi simili, sussistendo la condizione che tutto il territorio di una particolare nazione debba necessariamente essere dello stesso colore, quattro colori potrebbero non essere sufficienti. Concettualmente, un vincolo di questo tipo genererebbe una mappa non planare, rendendo il teorema non più valido. Consideriamo ad esempio una mappa semplificata:
In questa mappa, le due regioni indicate con A fanno parte della stessa nazione e devono avere la stessa colorazione. Questa mappa necessita di cinque colori, dal momento che le due regioni A sono complessivamente contigue a quattro altre regioni, ciascuna delle quali è adiacente a tutte le altre. Se A consistesse di tre regioni, potrebbero essere necessari sei o più colori; sfruttando regioni non connesse è pertanto possibile costruire mappe che richiedono un numero arbitrario ed infinitamente elevato di colori.
[modifica] Voci correlate
[modifica] Collegamenti esterni
- (EN) History of the Four Color Theorem in MacTutor
- (EN) 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)
- (EN) The Four Color Theorem di Robin Thomas
[modifica] 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
