Parlando di grafi (argomento della puntata in onda il 27 giugno), mi è venuto
in mente un problema classico chiamato problema dei quattro colori.
Supponete di avere una mappa geopolitica, con delle zone delimitate che
rappresentano i vari Stati, e di volerla colorare: ogni area deve essere
colorata e l'unico vincolo da rispettare è che non accada mai che due Stati
confinanti abbiano lo stesso colore (mentre è perfettamente lecito che Stati
diversi abbiano colori uguali, purché non siano confinanti).
Quanti colori servono? Beh, naturalmente se avete abbastanza pastelli diversi
riuscite sempre a risolvere il problema: per esempio, se avete a vostra
disposizione un colore diverso per ogni Stato il problema è banale. Ma
supponete di voler usare il minor numero di colori possibili. La questione
fu posta nella seconda metà dell'ottocento e fu per più di un secolo un vero e
proprio puzzle per molti matematici. Infatti è facile rendersi conto che ci
sono mappe per cui tre colori non sono sufficienti: per esempio, il Belgio
confina sia con la Germania che con la Francia, e inoltre la Germania e la
Francia sono confinanti fra loro, quindi per colorare Germania, Francia e
Belgio servono tre colori diversi. Inoltre, siccome il Lussemburgo confina con
tutti e tre gli Stati (Belgio, Germania e Francia), ne consegue che per
colorare anche il Lussemburgo servirà per forza un altro colore. Dunque,
quattro colori sono necessari. Ma sono sufficienti?
Se provate a mettervi a disegnare mappe "inventate" vi accorgerete presto che
è molto difficile creare una mappa in cui servano più di quattro colori. Anzi,
a dire la verità è impossibile. Cioè, quattro colori bastano per colorare
qualsiasi mappa.
Che c'entra questo con i grafi? Beh, c'entra. Supponete di trasformare ogni
nazione in un vertice di un grafo, e di mettere un arco fra due vertici se le
due nazioni sono fra loro confinanti. Il problema della colorazione della
mappa diventa un problema di colorazione del grafo: dovete colorarne i vertici
in modo che vertici adiacenti (cioè, che sono collegati da un arco) non
abbiano mai lo stesso colore. Ma di quali grafi stiamo parlando? In effetti,
da ogni mappa si può ricavare un grafo, ma qualunque grafo è ricavabile da una
mappa?
Ricordatevi che un grafo si disegna mettendo un pallino per ogni vertice, e
collegando con un segmento (o con una curva) tutte le coppie di vertici che
sono collegati da un arco. Ogni grafo si può quindi disegnare in molti modi
diversi, nel senso che la regola appena enunciata non dice dove devono essere
piazzati i vertici. Può accadere che disegnando un grafo in un certo modo
alcuni archi si intersechino, mentre spostando un po' i vertici si possano
evitare questi incroci. Se si riesce a fare questo si dice che il grafo è
planare. Un esempio di grafo non planare è il pentacolo (la stella a cinque
punte delle BR a cui avete aggiunto un cerchio che unisce ogni punta alle due
punte adiacenti): se anche spostate le punte o trasformate i segmenti che le
collegano in curve non riuscirete a non farne intersecare almeno due.
E' facile rendersi conto del fatto che i grafi che si ottengono da una mappa
sono grafi planari (per dirla in matematichese, sono "tutti e soli" i grafi
planari). Quindi il problema delle mappe si può riformulare come segue: qual è
il minimo numero di colori necessari a colorare un grafo planare?
Il passaggio da mappe a grafi può sembrare inutile e perfino perverso, ma è
vantaggioso nel senso che un grafo non contiene più nessun dettaglio
"ininfluente": non ci sono confini, non ci sono astruse linee di demarcazione
a zigzag che sono state ottenute seguendo il corso di qualche fiume o in base
a un qualche oscuro trattato di pace. Il grafo della mappa contiene solo le
informazioni indispensabili per la colorazione.
Già, ma anche come problema di colorazione di grafi la questione è complicata.
Il matematico inglese Alfred Kempe, nel 1877, credette di aver trovato una
dimostrazione (del fatto che quattro colori sono sufficienti) ma fu
sconfessato nel 1890 da Percy Heawood, che trovò un errore nella dimostrazione
di Kempe. Heawood riuscì a dimostrare, in compenso, che cinque colori erano
sufficienti. Questo, insieme al fatto che tre colori non bastano, lasciava
ancora uno spazio scoperto: bastano quattro colori, oppure c'è qualche mappa
(pardon: grafo) per cui ne servono cinque?
Si dovette aspettare quasi un secolo per ottenere una soluzione definitiva (?)
al problema: dopo una serie infinita di dimostrazioni sbagliate, nel 1976
Kenneth Apple e Wolfgang Hagen dimostrarono che quattro colori sono
sufficienti. In realtà, la dimostrazione di Apple e Hagen chiuse la questione
dei quattro colori, ma ne aprì un'altra, estremamente spinosa. Infatti, la
tecnica usata da Apple e Hagen fu assolutamente insolita per l'epoca: la loro
dimostrazione consisteva nel ridurre lo spazio di tutti i grafi planari
possibili a un insieme di "controesempi minimali". Se si fosse dimostrato che
quattro colori bastavano per colorare tutti questi controesempi, si sarebbe
ottenuto come risultato che quattro colori erano sufficienti in generale. I
controesempi minimali erano 1936: troppi da esaminare a mano! A quel punto,
chiesero aiuto a un computer: i due matematici scrissero un programma che
esaminò uno per uno tutti i 1936 esempi minimali e fu in grado di concludere
che erano tutti colorabili con quattro colori.
Questo approccio fu oggetto di grandi contestazioni all'epoca: per un
matematico, una dimostrazione è un ragionamento che deve convincere della
verità di un'asserzione e deve essere esaminabile da parte di un essere umano.
Il fatto che un pezzo della dimostrazione di Apple e Hagen fosse stato
prodotto da un computer e non potesse essere realisticamente verificato da un
singolo essere umano (i 1936 controesempi, una volta disegnati, riempivano ben
400 pagine!) fu considerata (e da molti lo è ancora) un'inaccettabile
violazione delle regole implicite nella nozione stessa di dimostrazione.
In realtà, questa obiezione non è del tutto peregrina: se una parte di una
dimostrazione è verificata da un programma per computer, occorre dimostrare a
parte che il programma usato è corretto. In effetti, il problema di convincere
la comunità matematica "ostile" rimane ancora aperto, ed è oggi estremamente
attuale (e pertinente per noi): che ruolo può avere un computer nell'assistere
il lavoro di un matematico? quanto e in che misura è accettabile che una
dimostrazione sia in parte prodotta o verificata solo mediante un programma?
Ci sono commenti.