Teorema dei 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.^[1] 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.^[2]

È immediato trovare mappe per le quali tre soli colori non sono sufficienti. Non è eccessivamente difficile dimostrare che ne bastano al più cinque.^[3] 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^[4].

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.^[5]

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.

Note

^ Non basta che abbiano solo uno o più punti isolati in comune, altrimenti una figura a forma di torta a fette sarebbe un controesempio.
^ In realtà, il risultato rimane valido qualora l'exclave non confini con stati che non siano comunque confinanti con il territorio di appartenenza - condizione che è rispettata sia dall'Italia (Campione d'Italia è interamente circondato da territorio svizzero), che dagli Stati Uniti d'America (l'Alaska confina unicamente con il Canada), che dalla Russia (Kaliningrad confina solo con Polonia e Lituania), ma ad esempio non dall'Angola (la cui Provincia di Cabinda confina, oltre che con la Repubblica Democratica del Congo, che la separa dal resto dell'Angola, anche con la Repubblica del Congo, che non confina con alcun'altra provincia angolana).
^ 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. Comunque, si veda in merito il teorema dei cinque colori.
^ Cfr. l'articolo "On the colourings of maps", Proc. Royal Geog. Soc. 1 (1879), p. 259-261.
^ Questa formula, inizialmente nota come congettura di Heawood, ha preso il nome di teorema della mappa colorata dopo che fu dimostrata da Gerhard Ringel e J.T.W. Youngs nel 1968.

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