Introduzione ai Grafi



Il problema dei quattro colori

Il problema dei quattro colori consiste nel colorare una qualsiasi carta geografica utilizzando soltanto quattro colori in modo tale che due generiche nazioni confinanti non abbiano mai lo stesso colore.

Alcune considerazioni: osserviamo che, negli studi compiuti a riguardo da Apel e Haken nel 1976, sono state messe in evidenza 1936 configurazioni critiche (una sorta di ipotetiche trappole o situazioni non desiderate), per le quali sono state impiegate 1200 ore di elaborazione con un calcolatore per dimostrare che in realtà ogni situazione critica può essere risolta con quattro colori.

Si palesa così la complessità della dimostrazione.

Procediamo per passi:


Introduzione alla Teoria Cromatica dei Grafi

Per affrontare analiticamente il problema dei quattro colori trasformiamo la nostra cartina geografica in una corrispondente struttura più agile, quale è il grafo.


Un grafo G è descritto da due insiemi V(G) e E(G) dove:
V(G) è l'insieme dei vertici di G
E(G) è l'insieme degli archi di G

un vertice è un oggetto semplice al quale è possibile associare un nome ed altre proprietà;
un arco è una connessione fra due vertici.

Traduciamo ora il problema dei quattro colori in termini di grafi.
La trasformazione che utilizziamo è detta corrispondenza Primale - Duale.
Il Primale è la cartina: per ognuna delle partizioni in cui è divisa la regione di spazio considerata individuiamo un elemento di rappresentanza (e.g. in una cartina geografica può essere la capitale), gli elementi di rappresentanza costituiscono l'insieme V(G) dei vertici del grafo G (il duale) che stiamo costruendo.
Gli elementi di rappresentanza di due partizioni confinanti sono uniti da un arco: l'insieme degli archi così ottenuto è il nostro E(G).


Primale Duale
Immagine del primale Immagine del duale

Osservazioni:


Il problema di colorare le regioni di una cartina geografica diventa allora equivalente al problema di colorare i vertici del grafo duale.
Il numero di colorazioni possibili dipende dal grafo e dal numero di colori a disposizione ed è definito dal polinomio cromatico del grafo.


Torna all'indice