Progetto 5: Coloriamo il mondoQual è il minimo numero di colori necessari per colorare la mappa data?

La funzione obiettivo La funzione obiettivo è data dalla somma di tutti i colori che si possono utilizzare nella colorazione di una mappa. Il Teorema dei 4 colori afferma infatti 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.

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.

min C1+C2+C3+C4Questa è la funzione obiettivo del problema, data quindi dalla minimizzazione del numero massimo di colori (4) che posso utilizzare per la colorazione della mappa. C ∈ {0,1}

…per comodità ho riportato la mappa in un grafo in cui ogni nodo rappresenta una regione.

VincoliPer prima cosa occorre definire la variabile X i C. X i C = 1 Se il nodo i è del colore C X i C = 0 Se il nodo i non è del colore C

VincoliOgni nodo deve essere colorato con un solo colore.Per ogni nodo avrò quindi : X11+X12+X13+X14 = 1X21+X22+X23+X24 = 1

Continuo cosi per tutti i nodi.

NODO COLORE

VincoliDue nodi adiacenti non devono essere mai colorati con lo stesso colore. Quindi se il nodo A è colorato del colore 1, XA1 vale 1, se contemporaneamente anche il nodo B, adiacente al nodo A è colorato del colore 1, XB1 vale 1 e il vincolo non è soddisfatto.XA1+XB1<= 1 In questo caso la regione A XA2+XB2<= 1 confina con la regione B.XA3+XB3<= 1XA4+XB4<= 1

Proseguo cosi per tutte le regioni confinanti.

VincoliSi collegano i vincoli precedenti alla funzione obiettivo facendo si che ogni volta si decida di colorare il nodo di un colore, di conseguenza le rispettive variabili C1, C2, C3, C4 assumono valore 1.C1 - XA1 > = 0 C2 - XA1 > = 0C1 - XB1 > = 0 C2 - XB1 > = 0C1 - XC1 > = 0 C2 - XC1 > = 0Continuo così per tutti i nodi.

RISULTATO FINALE Scrivendo il modello sul risolutore Excel possiamo avere una soluzione ottima. Per il problema preso in considerazione con 56 regioni si può

dedurre che è colorabile con 4 colori (Immagine a dx)L’immagine a sinistra invece ci mostra come una superficie di 9 regioni può

essere colorata con 3 colori.