Teorema dei quattro colori: storia, colorazioni di grafi e applicazioni

Il Teorema dei quattro colori è indubbiamente uno dei più famosi ed affinascinati
teoremi della Teoria dei Grafi. In questo articolo vediamo come è nato questo problema
ed i vari risultati che hanno portato alla dimostrazione del teorema, senza
ovviamente tralasciare il legame con le colorazioni di grafi, molto importanti anche
in virtù delle loro applicazioni. Se invece di leggerti l’articolo preferissi scaricarti il PDF e guardarlo con calma, lo puoi scaricare qui: Teorema quattro colori PDF.

Questo articolo è stato gentilmente scritto da Anita Pasotti,  Prof. Associato presso l’Università degli Studi di Brescia (Dipartimento DICATAM – Sezione di Matematica). Per informazioni, questa è la sua pagina :

 

http://anita-pasotti.unibs.it/

Teorema dei quattro colori. Data una qualsiasi carta geografica politica è
possibile colorare stati adiacenti con colori distinti utilizzando al più quattro colori.

Ad esempio in Figura 1 la cartina degli Stati Uniti d’America è stata colorata
usando esattamente quattro colori. Bisogna precisare che ogni stato deve essere
connesso e che per stati adiacenti si intendono due stati con almeno un segmento
di confine in comune e non solo un punto.

Teorema dei quattro colori

FIGURA 1. Colorazione Stati Uniti d’America

L’origine del problema risale al 1852 quando Francis Guthrie, studente di De
Morgan, colorando la cartina della contee britanniche in modo che stati adiacenti
avessero colori distinti si accorse che erano sufficienti quattro colori. Non riuscendo
a trovare una carta che richiedesse più di quattro colori, Francis iniziò a chiedersi se
fosse vero che OGNI mappa potesse essere colorata utilizzando solo quattro colori.
De Morgan propose la congettura alla London Mathematical Society chiedendo se
qualcuno fosse in grado di risolverla. Moltissimi matematici dedicarono anni della
loro vita allo studio di questo problema. Nonostante per molti anni nessuno riuscì
a provare la congettura, i vari tentativi portarono non solo a molti risultati inerenti
alle colorazioni di grafi, ma contribuirono anche allo sviluppo di altre aree
della Teoria dei Grafi.

La prima pubblicazione inerente all’argomento è di Cayley che nell’articolo “On the colouring of maps” del 1879 spiegò le difficoltà incontrate nel cercare di risolvere tale congettura. Nello stesso anno Alfred Bray Kempe, un avvocato londinese che studiò matematica a Cambridge sotto la guida di Cayley, pubblicò una dimostrazione della congettura che venne riconosciuta valida per ben undici anni, fino a quando, nel 1890, Percy John Heawood, un docente universitario della Durham England, vi trovò un errore. Nel lavoro “Map colouring theorem”, Heawood non solo confutò la dimostrazione di Kempe, ma dimostrò il Teorema dei cinque colori che afferma che ogni mappa può essere colorata usando al più cinque colori. L’errata dimostrazione di Kempe ebbe comunque un importante valore poichè per ottenerla introdusse le cosiddette catene di Kempe che sono state poi utilizzate nella dimostrazione definitiva del teorema.

 

Negli anni a seguire sono stati ottenuti vari risultati parziali da molti matematici. Heesch, ad esempio, sviluppò i concetti di riducibilità e di scaricamento, che si rivelarono essere indispensabili per l’ultima dimostrazione. E’ doveroso osservare che mentre l’idea di riducibilità era già stata studiata da altri ricercatori, quella dello scaricamento è dovuta interamente a Heesch, il quale riteneva che un adeguato sviluppo di questo metodo avrebbe portato alla soluzione del problema.

Ciò fu confermato nel 1977 quando Kenneth Appel e Wolfgang Haken, due matematici dell’Università dell’Illinois, pubblicarono la loro dimostrazione del Teorema dei quattro colori [1], [2]. Questa dimostrazione si basa sulla riduzione del numero infinito di mappe possibili ad un numero finito di configurazioni (per l’esattezza 1476) per le quali la validità del teorema viene verificata caso per caso grazie ad un complesso algoritmo informatico che utilizza proprio le catene di Kempe.

Fondamentale fu l’aiuto di Koch, uno studente di informatica, che migliorò man mano il programma. Il programma definitivo aveva avuto ben 500 variazioni da quello originario e fu eseguito su due macchine diverse con algoritmi indipendenti al fine di ridurre al minimo la possibilità di errore. Per analizzare tutti i casi possibili i computer impiegarono circa 50 giorni e servirono più di 500 pagine per trascrivere a mano tutte le verifiche che costituivano la dimostrazione.

L’utilizzo di algoritmi informatici nella dimostrazione di Appel e Haken scatenò grandi polemiche nel mondo scientifico, tanto che alcuni matematici ne contestarono la validità non solo per l’impossibilità di verifica manuale, ma anche perchè la logica afferma che è impossibile dimostrare la correttezza dell’algoritmo.

Fino ad oggi nell’algoritmo non è stato trovato alcun errore, ad ogni modo anche se
ne viene accettata la validità, la dimostrazione non è di certo considerata elegante a
tal punto da essere stata paragonata ad un elenco telefonico. Nel 1997 N. Robertson,
D.P. Sanders, P.D. Seymour e R. Thomas [5] proposero una dimostrazione al
computer che consiste in una riduzione del numero di configurazioni da 1476 a 633,
ma anche la loro dimostrazione non è verificabile manualmente. Infine, nel 2000,
Ashay Dharwadker [6] propose una nuova dimostrazione del teorema che richiede
l’utilizzo della Teoria dei Gruppi.

 

Abbiamo quindi visto come un problema apparentemente così semplice sia stato
in realtà irrisolto per più di un secolo. Vediamo ora come esso possa essere formulato
in termini di colorazioni di grafi. Per fare ciò ci servono alcune nozioni
di base [3]. Un grafo $G$ è una coppia $(V, S)$ dove $V$ è un insieme di punti detti
vertici ed $S$ è un insieme di coppie non ordinate di punti detti spigoli. Sia
ad esempio $G$ il grafo rappresentato in Figura 2. Si ha $V (G) = \{0, 1, 2, 3, 4\}$ e
$S(G) = \{[0, 1], [0, 2], [0, 3], [1, 2], [2, 3], [3, 4]\}$. Due vertici si dicono adiacenti se c’è lo spigolo che li congiunge. Quindi, nel grafo in Figura 2 il vertice 0 è adiacente ai vertici 1, 2, 3, mentre il vertice 4 è adiacente solo al vertice 3.

Colorazione grafiColorazione grafo planare

 

FIGURA 2. Un esempio di grafo ed una sua 3-colorazione

 

Una colorazione di un grafo è una funzione che associa ad ogni vertice un colore in modo che vertici adiacenti abbiano colori distinti. Con c-colorazione si intende una colorazione che utilizza esattamente $c$ colori distinti. Si dice numero cromatico di un grafo $G$ il minimo $c$ per cui esiste una $c$-colorazione di $G$. Ad esempio il grafo in Figura 2 ha numero cromatico 3, a fianco abbiamo infatti una sua 3-colorazione ed è immediato osservare che una 2-colorazione non esiste.

Piccola parentesi esterna all’articolo originale. Se sei interessato/a ad approfondire la teoria introduttiva ai grafi, qui puoi trovare una bella playlist di video, sono davvero molto chiari 😉 , inoltre avevo scritto un articolo sul problema dei ponti di Konigsberg, lo puoi trovare qui: I 7 ponti di Konigsberg

Per enunciare il Teorema dei quattro colori in termini di colorazioni di grafi basta
osservare che ad ogni mappa geografica può essere associato un grafo nel seguente
modo. Rappresentiamo ogni stato della mappa con un punto in corrispondenza della
propria capitale e uniamo due punti se e solo se le capitali che essi rappresentano
corrispondono a stati adiacenti. In tal modo trasformiamo la carta in un grafo i cui
vertici sono le capitali mentre gli spigoli sono i segmenti congiungenti le capitali di
stati adiacenti. Si può dimostrare che il grafo che si ottiene in tal modo è sempre
planare, cioè si può disegnare in modo che i suoi spigoli si incontrino solo nei vertici.

Risulta quindi evidente che il Teorema dei quattro colori può essere enunciato
nel seguente modo: ogni grafo planare ammette una 4-colorazione.
Il filone delle colorazioni di grafi, che si è sviluppato ovviamente anche grazie
allo studio del problema dei quattro colori, ha svariate applicazioni concrete.

Ricordiamo, ad esempio, quella ai numerosi problemi di schedulazione [4]. In tutti
questi problemi si deve assegnare un dato insieme di compiti a degli spazi temporali,
ma alcune coppie di compiti sono in conflitto, cioè non possono essere assegnate
allo stesso spazio temporale. Per risolvere il problema si costruisce il grafo i cui
vertici rappresentano i compiti e due vertici sono adiacenti solo se rappresentano
una coppia di compiti in conflitto. Il numero cromatico del grafo è esattamente il
tempo ottimale per finire tutti i compiti senza conflitti. I dettagli del problema di
schedulazione definiscono la struttura del grafo, vediamo come tramite un esempio
concreto.

Consideriamo il problema di schedulazione del diario degli esami universitari:
Qual è il minimo numero di giorni necessario per far sostenere ad $n$ studenti
$m$ esami, in maniera tale che nessuno studente debba sostenere due esami lo stesso
giorno? Per rappresentare il problema consideriamo il grafo i cui vertici rappresentano
gli $m$ esami e due vertici sono adiacenti se c’è almeno uno studente che
deve sostenere entrambi gli esami rappresentati da quei due vertici. È immediato
vedere che il numero cromatico del grafo così ottenuto è proprio il minimo numero
di giorni necessari. Altri importanti problemi di schedulazione sono ad esempio
quello dell’assegnazione di aeromobili ai voli o quello dell’allocazione delle ampiezze
di banda alle stazioni radio.

Infine concludiamo osservando che anche molti problemi matematici ben noti,
sia ricreativi che non, possono essere formulati in termini di colorazioni di grafi.
Ad esempio il sudoku può essere visto come il completamento di una 9-colorazione
(ogni numero corrisponde ad un colore) di un assegnato grafo con 81 vertici (ogni
cella corrisponde ad un vertice).

Riferimenti bibliografici

[1] K. Appel e W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977), 429–490.
[2] K. Appel e W. Haken, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977), 491–567.
[3] F. Harary, Graph Theory, Addison-Wesley, Reading MA, 1969.
[4] D´aniel Marx, Graph colouring problems and their applications in scheduling, in Periodica Polytechnica, Electrical Engineering, 48 (2004), 11–16,
[5] N. Robertson, D. P. Sanders, P. D. Seymour e R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B. 70 (1997), 2–44.
[6] A. Dharwadker, A New Proof of the Four Colour Theorem,
http://www.geocities.com/dharwadker/, 2000.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.