Matematica Discreta
Lezione del giorno 22 gennaio 2009 Colorazione di un grafo
Abbiamo visto che il problema della colorazione delle regioni di una mappa geografica può essere interpretato in termini di teoria dei grafi: 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.
E’ bene mettere in evidenza 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 geografica), se V è l’insieme dei vertici del grafo e se C è un insieme astratto, una colorazione del grafo con colori in C è una funzione f: V C che associa ad ogni vertice del grafo un elemento dell’insieme (quindi un “colore”) 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.
Con questo linguaggio il “teorema dei 4 colori” afferma che: il numero cromatico del grafo associato ad una qualunque carta geografica è 4.
Esempio: nel seguente grafo con 5 vertici e
a b
c d
si può ottenere per esempio una colorazione con 5 colori (con C={1,2,3,4,5}) 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, al vertice e il colore 5.
Ma si può ottenere anche 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, al vertice e il colore 2.
Possiamo ancora risparmiare sul numero di colori, ed ottenere 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 3, al vertice d il colore 1, al vertice e il colore 2.
D’altra parte è impossibile ottenere una colorazione con 2 colori perché i 3 vertici b,c,d (essendo a 2 a 2 adiacenti fra loro) necessitano di 3 colori differenti. Dunque si conclude che il numero cromatico di questo 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 in cui non tutti i vertici sono isolati (quindi con numero cromatico >1) . Allora:
il numero cromatico del grafo è 2 tutti i cammini ciclici nel grafo hanno lunghezza pari.
Per dimostrare tale teorema dobbiamo però introdurre il concetto di componente connessa in un grafo.
Componenti connesse di un grafo
Anche se un grafo non è connesso, esso può essere suddiviso in grafi connessi più piccoli, come vedremo definendo le cosiddette componenti connesse di un grafo.
Definiamo dapprima un tipo di cammino convenzionale (che ha lo stesso ruolo dell’insieme vuoto nell’insiemistica): fissato un vertice w in un grafo, definiamo per convenzione il cammino vuoto (di lunghezza zero) che unisce il vertice w con sé stesso senza percorrere alcun arco.
Sia dato un grafo qualunque. Definiamo una relazione R nell’insieme dei vertici V mediante il predicato P(x,y)=”esiste almeno un cammino che unisce x con y”.
Si verifica facilmente che tale relazione è di equivalenza.
La proprietà riflessiva deriva dall’esistenza del cammino vuoto che unisce un vertice con sé stesso.
La simmetrica deriva dalla possibilità di percorrere un cammino da v a w in senso inverso, ottenendo un cammino da w a v.
Infine la transitiva dall’osservazione che percorrendo di seguito 2 cammini da v a w e da w a z, si ottiene un cammino da v a z.
Ogni classe di equivalenza della relazione R è detta componente connessa del grafo.
Essendo classi di equivalenza, le componenti connesse di un grafo formano una partizione dell’insieme dei vertici V.
Dati 2 vertici v,w, se essi appartengono alla stessa componente connessa sono associati fra loro nella relazione suddetta, quindi fra vertici della stessa componente connessa esiste sempre almeno un cammino. In particolare ogni componente, considerata come grafo a sé stante (nel senso che si considerano i suoi vertici e solo gli archi che li collegano) è un grafo connesso.
Ovviamente un grafo connesso ha 1 sola componente connessa, coincidente con l’intero grafo.
Esempio: dato il seguente grafo con 10 vertici:
1 2 3
a b c d e f m 4 5 6 7
g h i
se calcoliamo le classi di equivalenza otteniamo 4 classi distinte [a] = {a,b}, [c] = {c,d,g}, [e] = {e,f,h,i}, [m] = {m}
Dunque il grafo ha 4 componenti connesse formate rispettivamente dai vertici {a,b} (e dall’arco 1), dai vertici {c,d,g} (e dagli archi 2,4), dai vertici {e,f,h,i} (e dagli archi 2,5,6,7), e dal vertice isolato m (ovviamente ogni vertice isolato forma sempre, da solo, una componente connessa, in quanto è associato solo a sé stesso). Ognuna di tali componenti, considerata come grafo a sé stante, è un grafo connesso, anche se il grafo originario non è connesso.
