Primi elementi della teoria dei grafi

Il problema dei quattro colori

Quanti colori servono per colorare una qualunque carta geografica in modo che due stati confinanti non abbiano lo stesso colore? Questo problema fu posto da Francis Guthrie nel 1852 il quale studiando alcune carte geografiche aveva cercato inutilmente di dimostrare la sua congettura:

sono sufficienti solo quattro colori

Il quesito sembra un semplice rompicapo che chiunque può facilmente risolvere, eppure per più di un secolo molti matematici tentarono invano di risolverlo. Per questo motivo è diventato famoso con l'appellativo "il problema dei quattro colori". Innanzitutto, bisogna stabilire che il confine tra due stati non deve ridursi a un solo punto altrimenti quattro colori non bastano, ad esempio, una carta geografica a forma di torta tagliata a fette richiederebbe tanti colori quante sono le fette.

Inoltre, gli stati non devono essere formati da territori separati, cioè non devono avere delle enclavi come ad esempio Gibilterra che ha il confine con la Spagna ma fa parte dello stato britannico.

Non è difficile trovare una normale carta geografica in cui ci siano quattro stati oppure quattro regioni ciascuna confinante con le altre tre, ad esempio gli stati europei: Lussemburgo, Belgio, Germania e Francia confinano ognuno con gli altri tre.

In questi casi è necessario utilizzare effettivamente quattro colori.

Sono necessari quattro colori anche quando uno stato (una regione o una provincia) è circondata da un numero dispari di altri stati che confinano reciprocamente.

A questo punto sorge una domanda ovvia: ma se cinque stati confinano ciascuno con gli altri quattro allora occorono necessariamente almeno cinque colori e quindi la congettura dei quattro colori è falsa? Augustus De Morgan scoprì che è materialmente impossibile che cinque stati confinano ciascuno con gli altri quattro e questo si dimostra facilmente utilizzando la teoria dei grafi. Una carta geografica è un grafo planare i confini sono gli spigoli e i vertici sono i punti in cui due o più confini si incontrano. La congettura dei quattro colori è quindi un problema interno alla teoria dei grafi e può essere riformulato in modo equivalente utilizzando il linguaggio dei grafi. Per questo tipo di problema si preferisce ragionare sul grafo duale della carta geografica perchè è più leggibile e contiene tutte le informazioni che occorrono. Vediamo come si può ottenere il duale di una carta geografica. Supponiamo di avere la seguente carta geografica.

Inseriamo un vertice in ogni stato, ad esempio in corrispondenza della capitale, e uniamo due vertici con uno spigolo se e solo se gli stati corrispondenti hanno un confine comune.

Si ottiene così un grafo planare duale alla carta geografica.

Nel passaggio tra la carta geografica e il corrispondente grafo duale gli stati si trasformano in vertici e i confini si trasformano in spigoli. Possiamo, ora, riformulare la congettura dei quattro colori nel linguaggio dei grafi in questo modo:

Con solo quattro colori è possibile colorare i vertici di un grafo planare in modo che due vertici adiacenti abbiano colori diversi?

Supponiamo che c'è una carta geografica in cui cinque stati confinano ciascuno con gli altri quattro e costruiamo il suo grafo duale. Quest'ultimo dovrà contenere al suo interno un sottografo avente cinque nodi ognuno dei quali deve essere connesso con gli altri quattro e cioè, il grafo duale dovrà contenere una copia del grafo K₅. Sappiamo, però, che il grafo K₅ non è planare e quindi anche il grafo duale dovrà essere necessariamente non planare e ciò contraddice il fatto che il duale di un grafo planare è planare. In conclusione il fatto che K₅ non è planare significa che non è possibile che in una carta geografica ci siano cinque stati tutti adiacenti fra loro. Questo però non dimostra la congettura dei quattro colori, dimostra semplicemente che in un grafo ogni insieme di cinque nodi può essere colorato con quattro colori diversi che può essere tradotto in un altro modo: in una carta geografica ogni insieme di cinque stati può essere colorato con quattro colori diversi. Ad esempio, se consideriamo il grafo duale precedente possiamo colorare ogni gruppo di cinque nodi con quattro colori diversi.

Nel 1879 Alfred Bray Kempe pubblicò una dimostrazione della congettura dei quattro colori che fu ritenuta valida ma undici anni dopo Percy John Heawood trovò un errore che invalidava la dimostrazione di Kempe. Heawood utilizzando il ragionamento di kempe dimostrò che un grafo planare poteva essere colorato utilizzando al massimo solo cinque colori. Negli anni successivi furono fatti molti altri tentativi per trovare una dimostrazione per i quattro colori tutti destinati a fallire. La congettura dei quattro colori si dimostrò un rompicapo estremamente complicato però tutti questi tentativi per risolverlo permisero di approfondire la conoscenza dei grafi scoprendo nuove proprietà. Solo nel 1976 Kenneth Appel e Wolfgang Haken dimostrarono che la congettura era vera. I due matematici riuscirono a ridurre a 1476 il numero delle possibili configurazioni di carte geografiche che dovettero analizzare caso per caso con l'aiuto indispensabile di un computer e furono necessarie più di 500 pagine per trascrivere le verifiche che il computer aveva compiuto lavorando per 1200 ore. Questa dimostrazione creò perplessità, polemiche e contestazioni nel mondo scientifico; per la prima volta il difficile compito di una dimostrazione era stata affidata a una macchina ed era umanamente impossibile fare una verifica manuale.