Matematica Discreta Lezione del giorno 23 gennaio 2009

Matematica Discreta

Lezione del giorno 23 gennaio 2009

Per calcolare il numero cromatico di un grafo, possiamo servirci delle sue componenti connesse nel modo seguente: dalla teoria delle relazioni di equivalenza sappiamo che, dati 2 vertici v,w in componenti connesse diverse (quindi in classi di equivalenza diverse) essi non sono associati fra loro nella relazione di equivalenza che definisce tali classi, quindi non esiste un cammino che unisce v e w, e a maggior ragione non esiste un arco che unisce v,w, ossia v,w non sono adiacenti;

nella colorazione dei vertici del grafo possiamo allora colorare i vertici di ogni componente connessa, potendo riutilizzare gli stessi colori nelle diverse componenti. Da tale ragionamento segue che il numero cromatico del grafo sarà il più grande dei numeri cromatici delle componenti connesse (la componente connessa che “pretende” più colori ha la prevalenza).

Nel grafo esaminato nell’esempio della lezione precedente:

1 2 3

a b c d e f m 4 5 6 7

g h i

si verifica facilmente che i numeri cromatici delle 4 componenti connesse sono 2, 2, 3, 1, dunque il numero cromatico dell’intero grafo è 3.

Possiamo ora dimostrare il teorema su l numero cromatico 2:

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.

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.

(): Calcoliamo il numero cromatico di ogni singola componente connessa del grafo. Se la

componente considerata ha un solo vertice (isolato) il suo numero cromatico è 1. Consideriamo

quindi il caso in cui la componente considerata abbia più di 1 vertice: dimostreremo che tale

componente ha numero cromatico 2, e quindi otterremo la tesi (il numero cromatico del grafo sarà

2, il più grande dei numeri cromatici delle sue componenti). Supponiamo quindi di dovere colorare i

vertici di tale componente connessa (avente più di 1 vertice). 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 contemporaneamente un cammino da v a w di lunghezza pari e anche un cammino da v a w di lunghezza dispari (altrimenti, percorrendo di seguito i 2 cammini, otterremmo 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; usiamo allora la seguente strategia per colorare w: coloriamo w con il colore 1 se i cammini da v a w sono di lunghezza pari, altrimenti coloriamo w con il colore 2, se i cammini da v a w sono di lunghezza dispari. Facendo variare il vertice w (fra quelli ≠v), 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. Se uno dei vertici w,z è il vertice di riferimento v allora è ovvio (se v è collegato con un arco ad un altro vertice w, allora esiste un cammino di lunghezza dispari 1 da v a w, quindi per la nostra strategia il vertice w ha colore 2 diverso dal colore 1 del vertice v). Supponiamo dunque che i vertici w,z adiacenti siano entrambi ≠v: se per assurdo w,z avessero per esempio lo stesso colore 2 (nella nostra strategia di colorazione), esisterebbe da w a v un cammino di lunghezza dispari, e da z a v un cammino di lunghezza dispari; ma allora (percorrendo di seguito questi 2 cammini e poi l’arco che unisce w e z) si otterrebbe in totale un cammino ciclico di lunghezza dispari+dispari+1=dispari , contro l’ipotesi. Analoga contraddizione si ha se si suppone per assurdo che w,z abbiano lo stesso colore 1.

Grafi semplici e multipli.

Nella definizione più formale di grafo, abbiamo detto che esiste una funzione (detta funzione di adiacenza) dall’insieme A degli archi all’insieme V

di tutti gli insiemi contenenti 2 vertici: in pratica tale funzione associa ad ogni arco i 2 vertici estremi dell’arco.

Notiamo però che, nella nostra definizione di grafo, non è detto che la funzione di adiacenza sia

iniettiva, cioè può avvenire anche che 2 archi diversi abbiano gli stessi vertici estremi (per esempio

nel caso del grafo dei ponti, gli archi 1,2 hanno gli stessi estremi a,b). Se la funzione di adiacenza è

iniettiva si dice che il grafo è semplice, mentre se la funzione di adiacenza non è iniettiva si dice

che il grafo è multiplo (o è un multigrafo) : in un grafo semplice, comunque presi due vertici

distinti, vi è al massimo 1 arco che li ha come estremi, quindi o essi non sono adiacenti (nessun arco

li ha come estremi) oppure esattamente 1 arco li ha come estremi..