Matematica Discreta I Lezione del giorno 12 dicembre 2007 Colorazione di un grafo

Matematica Discreta I

Lezione del giorno 12 dicembre 2007 Colorazione di un grafo

Nell’800 fu posto il seguente problema: qual è il minimo numero di colori necessario per colorare le regioni di una qualunque mappa geografica, con la condizione che regioni confinanti abbiano colori diversi ?

Tale problema fu risolto nel 1977 da Appel e Haken, con la dimostrazione del “teorema dei 4 colori”, il quale afferma che 4 colori bastano per qualunque mappa geografica.

Si può interpretare tale problema nel linguaggio della teoria dei grafi: infatti a una mappa geografica si può associare un grafo in cui ogni vertice rappresenta una regione, e due vertici sono collegati da un arco se le regioni corrispondenti sono confinanti.

Per esempio alla seguente mappa geografica con 6 regioni:

si può associare il seguente grafo con 6 vertici:

a b c

d e f

Notare che con tale procedimento, al variare delle diverse mappe geografiche, non si ottengono tutti i possibili grafi, ma solo grafi con proprietà particolari (detti grafi “planari”).

Dal problema della colorazione delle mappe nasce in modo naturale la definizione di colorazione di un grafo.

Dato un grafo qualunque (non necessariamente un grafo associato ad una mappa) , una colorazione è una funzione che associa ad ogni vertice del grafo un elemento di un insieme C (detto insieme dei colori) tale che a vertici adiacenti (cioè collegati da un arco) siano associati colori diversi.

Il numero cromatico di un grafo è il minimo numero di colori che servono per ottenere una colorazione del grafo, quindi è la minima cardinalità di un insieme C tale che esista una colorazione del grafo con colori in C.

a b c

d e f

Con questo linguaggio il “teorema dei 4 colori” afferma che: il massimo numero cromatico del grafo associato ad una qualunque carta geografica è 4.

Esempio: nel seguente grafo con 4 vertici a b

c d

si può ottenere per esempio una colorazione con 4 colori (con C={1,2,3,4}) associando al vertice a il colore 1, al vertice b il colore 2, al vertice c il colore 3, al vertice d il colore 4.

Ma si può ottenere anche una colorazione con 3 colori (con C={1,2,3}) associando al vertice a il colore 1, al vertice b il colore 2, al vertice c il colore 1, al vertice d il colore 3. D’altra parte è impossibile ottenere una colorazione con 2 colori perché i 3 vertici b,c,d necessitano di 3 colori differenti. Dunque il numero cromatico del grafo è 3.

Caratterizziamo i grafi con “basso” numero cromatico. E’ ovvio che un grafo ha numero cromatico 1 se e solo se ha solo vertici isolati (quindi se e solo se non vi sono archi nel grafo). Per il numero cromatico 2 vi è il seguente risultato:

Teorema. Sia dato un grafo . Allora:

il numero cromatico del grafo è 2  tutti i cammini ciclici nel grafo hanno lunghezza pari.

Dimostrazione:

(): Supponiamo per assurdo che esista nel grafo un cammino ciclico di lunghezza dispari, che rappresentiamo schematicamente come segue:

v

v

v

……… v

a

a

a

La lunghezza del cammino (numero degli archi percorsi) è per assurdo n dispari. Per ipotesi è possibile colorare i vertici del grafo usando solo 2 colori 1,2: ma se per esempio il vertice v

è colorato con 1, necessariamente il vertice v

è colorato con 2, il vertice v

è colorato con 1 e così via, cioè i vertici con indice pari sono colorati con il colore 2, i vertici con indice dispari con il colore 1. Essendo n dispari, il vertice finale v

di indice dispari dovrebbe essere colorato con il colore 1, ma v

è collegato tramite l’arco a

con il vertice v

, che era già stato colorato con il colore 1, contraddizione.

(): Per dimostrare la tesi, dobbiamo colorare i vertici del grafo usando solo 2 colori 1,2. Poiché vertici di 2 componenti connesse diverse non sono collegati da archi, possiamo colorare separatamente i vertici di ogni singola componente, utilizzando gli stessi colori nelle altre componenti. Supponiamo quindi di dovere colorare i vertici di una generica componente connessa.

Scegliamo a caso nella componente un vertice v “di riferimento” e coloriamolo con il colore 1.

Scelto nella componente un qualunque vertice w≠v, coloriamo w con la seguente strategia: essendo

v,w nella stessa componente , certamente esiste qualche cammino da v a w; ma non può esistere un

cammino da v a w di lunghezza pari e anche un cammino da v a w di lunghezza dispari (altrimenti

esisterebbe in totale un cammino ciclico di lunghezza pari+dispari=dispari, contro l’ipotesi);

dunque i cammini da v a w sono tutti di lunghezza pari o tutti di lunghezza dispari; coloriamo allora w con il colore 1 se i cammini da v a w sono di lunghezza pari, altrimenti coloriamo w con il colore 2. Facendo variare il vertice w, coloriamo così tutti i vertici della componente. Dobbiamo però verificare che due vertici w,z adiacenti (cioè collegati da un arco) non abbiano mai lo stesso colore:

ma se per assurdo i vertici w,z avessero per esempio lo stesso colore 2, esisterebbe per costruzione

da w a v un cammino di lunghezza dispari, e da z a v un cammino di lunghezza dispari; ma allora

esisterebbe in totale un cammino ciclico di lunghezza dispari+dispari+1=dispari , contro l’ipotesi.