Teorema dei quattro colori

Esempio di mappa a quattro colori

Il teorema dei quattro colori è un teorema di matematica che 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 una linea di confine in comune. Ciascuna regione deve inoltre occupare un territorio connesso, cioè non deve essere formata da due o più parti sconnesse, ovvero con la presenza di exclavi.

È immediato trovare mappe per le quali tre soli colori non sono sufficienti. Non è eccessivamente difficile dimostrare che ne bastano al più cinque. Tuttavia dimostrare che ne siano sufficienti quattro è particolarmente complesso, tanto che la dimostrazione di questo teorema ha richiesto, tra l'altro, un estensivo ricorso al computer, per una delle prime volte nella storia della matematica.

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.

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 un'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 1936 configurazioni (poi ulteriormente ridotte a 1476), 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 algoritmi 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 la difficoltà di avere la certezza che l'algoritmo fosse implementato correttamente. Ad ogni modo, nonostante le accuse di scarsa "eleganza", nell'algoritmo non è mai stato trovato alcun errore.

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.

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 $\,\chi$ della superficie, in accordo con la formula:

$p(\chi )=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,$

dove le parentesi $\lfloor \cdot \rfloor$ indicano la funzione parte intera. Per esempio, il toro ha caratteristica di Eulero $\chi =0$ e $p=7$: saranno pertanto necessari al massimo sette colori per colorare qualsiasi mappa su una superficie toroidale.

La sola eccezione alla formula è la bottiglia di Klein, la quale ha caratteristica di Eulero uguale a 0 e richiede sei colori.

Carte geografiche alle quali il teorema non è applicabile

Il teorema si applica a mappe suddivise in regioni connesse e reciprocamente indipendenti. Nelle carte geografiche politiche esistono stati il cui territorio, anche escludendo le isole, è costituito da un insieme di regioni non connesse: ne sono esempi l'Alaska come parte degli Stati Uniti e l'exclave di Kaliningrad, appartenente alla Russia ma completamente circondata dalla Polonia e dalla Lituania. In casi simili, imponendo la condizione che tutto il territorio di uno Stato debba necessariamente essere dello stesso colore, si modificano le premesse alla base del teorema e quattro colori potrebbero non essere sufficienti.

Concettualmente, un vincolo di questo tipo genererebbe una mappa non planare. Consideriamo ad esempio una mappa semplificata:

In questa mappa, le due regioni indicate con $A$ fanno parte dello stesso stato 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 arbitrariamente elevato di colori.

Bibliografia

• Kenneth Appel, Wolfgang Haken, John Koch, Every Planar map is Four Colorable, 1977, 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, Every Planar Map is Four-Colorable Providence, 1989, RI: American Mathematical Society
• Saaty, Kainen, The Four Color Problem: Assaults and Conquest, ISBN 0-486-65092-8

Voci correlate

• Teoria dei grafi
• Teorema dei cinque colori
• Topologia

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul teorema dei quattro colori

Collegamenti esterni

• (EN) Robert Osserman, four-colour map problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) map-colouring problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Teorema dei quattro colori, su MathWorld, Wolfram Research.
• (EN) Teorema dei quattro colori, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) four colour map theorem, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
• (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
• (EN) A New Proof of the Four Colour Theorem, su geocities.com. URL consultato il 21 novembre 2007 (archiviato dall'url originale il 18 ottobre 2007). di Ashay Dharwadker