Matematica discreta

V6

Rispetto alla scelta di prendere un orario differente per ogni lezione, con questa scelta si sono risparmiate 2 ore di tempo, infatti vengono impiegate 4 ore anziché 6.

Si è attribuita una funzione c all'insieme dei vertici V tale che da questo insieme si è passato all'insieme dei numeri naturali N (nell'esempio insieme degli "orari"), con la proprietà che se due vertici sono adiacenti c(v) ≠ c(vi).

In realtà si parla di colorazione di un grafo perché l'insieme di arrivo può essere pensato come l'insieme dei colori associato ad ogni vertici. Nel esempio ogni orario può essere visto come un colore differente, di conseguenza i vertici corrispondenti vengono colorati di tali colori.

1. ore 09 colore rosso, V1
2. ore 10 colore giallo, V2
3. ore 11 colore verde, V3
4. ore 12 colore blu, V4

Definizione:

Una colorazione di vertici per un grafo è una funzione c tale che c: V → N.

proprietà che se ~ (se sono adiacenti).≠( ) ( )c v c v v vi j i j

Ci si chiede se però la colorazione che è stata scelta sia proprio la più conveniente, cioè di quella scelta a 4 colori, riesco ad averne una ancora migliore? Nell'esempio riportato è possibile eliminare un colore scegliendo in questo modo una soluzione più ottimale.

1. ore 09 colore rosso, V V1 5
2. ore 10 colore giallo, V V2 4
3. ore 11 colore blu, V V3 6 Matematica Discreta 69

Quindi dal grafo avente 4 colorazioni si è passato al seguente con 3, risparmiando così un'altra utilissima ora.

Definizione

Un grafo si dice K colorabile se esiste una colorazione che usa K colori.

Definizione

Dato un grafo G=(V,E) si definisce il numero cromatico, e si indica con Χ(G), il minimo K tale che G sia K colorabile. Χ = 3, ovvero:

Nell'esempio proposto Χ(G) perché si sono usati 3 colori per colorare il grafo; Χ ≤ 3G perché essendoci la

presenza di un triangolo all'interno del grafo, devo usare Χ ≥ ( ) 3Galmeno 3 colori per colorare il grafo.:Χ =( )G K

esiste una colorazione con K colori;

ogni altra colorazione usa almeno K colori.

Matematica Discreta 70Esercizio

Determinare: , ,Χ Χ Χ( ) ( ) ( )K C Wn n n

1) Ricordando che Kn è un grafo completo con n vertici collegati fra di loro, risulta semplice affermare che c'è bisogno di n colori per colorare il grafo.=nΧ ( )K n

2) Cn è un ciclo con n vertici. Bisogna tener presente che il numero di vertici può cambiare. essere pari o dispari, quindi a seconda dei due casi Χ ( )C n

Se il numero di vertici è dispari è necessario usare 3 colori (si procede in modo alternato con due colori ma all'ultimo vertice bisogna usarne uno nuovo) mentre se è pari alternamente si usano 2 soli colori senza problemi.

3) Wn è un grafo fatto a forma di ruota e come Cn può avere un numero di

Qui di seguito viene riportato un algoritmo in grado di determinare la colorazione di un grafo G=(V,E). Si faccia attenzione al fatto che questo algoritmo non trova il numero cromatico (il numero minimo di colori), anche se alle volte la soluzione trovata può coincidere con esso.

L'algoritmo è il seguente:

1. Si ordina l'insieme dei vertici V = {v1, v2, ..., vn}
2. Si associa il primo colore al primo vertice v1 (c1)
3. Al vertice j-esimo si associa l'insieme S, cioè l'insieme dei colori assegnati ai vertici vicini di vj. Al vertice vj va assegnato il minimo colore non appartenente a S.

Per capire il procedimento dell'algoritmo Greedy, si userà l'esempio visto in precedenza:

1. I vertici sono già stati ordinati come in figura "si associa a

v1 il primo colore”2. =( ) 1c v13. Quale colore è possibile associare a v2? Si crea l’insieme S nel quale=( ) ?c v 2vanno inseriti i colori associati ai vicini (vertici adiacenti) di v2.{ }= 1Sil minimo colore non appartenente a S è 2 quindi si associa al vertice v2 tale colore.=( ) 2c v 24. Si segue lo stesso ragionamento decritto al punto 2 per trovare il colore al verticev3. { }= → =( ) 1 0c v S3L’unico vertice vicino a v3 è v5 al quale ancora non è stato associato alcun colore, quindil’insieme S risulta essere vuoto. Essendo vuoto l’insieme S, il piu’ piccolo colore nonappartenente all’insieme è 1,( ma in realtà nulla vieterebbe di usare il 2).Matematica Discreta 72{ }5. = → =( ) 2 1c v S4 { }6. = → =( ) 3 1, 2c v S5 { }7. = → =( ) 4 1, 2,3c v S6Tramite questo algoritmo si è riusciti a colorare il grafo usando 4 colori, ma come è statodetto in precedenza il grafo

Il tuo compito è formattare il testo fornito utilizzando tag html.

ATTENZIONE: non modificare il testo in altro modo, NON aggiungere commenti, NON utilizzare tag h1;

colorerà il vertice i-esimo.Teorema di Brooks χ1. Se G non è completo e non è un ciclo dispari, allora χ(G) ≤ Δ(G)Il primo teorema afferma che per un qualsiasi grafo G risulta che, se Δ(G) è il massimo grado di G, allora il numero cromatico può essere al più uguale a Δ(G)+1, ovvero i colori che χ(G) servono per poter colorare un grafo non possono mai superare il numero Δ(G)+1. In particolare se il grafo in questione è un grafo completo o un ciclo di lunghezza dispari, vale solamente l'uguaglianza: χ(G) = Δ(G)+1Il teorema di Brooks, ci assicura che solo per i grafi completi ed i cicli dispari vale l'uguaglianza, in altre parole per tutti gli altri grafi non completi e cicli pari vale χ(G) ≤ Δ(G)Ad esempio si prenda in considerazione un grafo regolare e completo qualsiasi come quello in figura:Da questo grafo si può osservare che il grado massimo è 3, in particolare essendo un grafo

Completo ogni vertice ha grado 3, ma quel che conta è che per poterlo colorare ho bisogno di un certo numero di colori che non supera il 4 e, in effetti 4 è proprio il numero esatto di colori utili.

Anche il grafo riportato di seguito è un grafo regolare (ma non completo). Il grado di G è pari a 2, e come visto dal teorema di Brooks, trattandosi di un grafo non completo e di un ciclo pari, il numero cromatico è al più uguale al grado massimo di v in V, cioè k=2; in effetti il numero cromatico di questo esempio è proprio 2, quindi vale la relazione: χ ≤ ( )G K

Considerando l'algoritmo greedy si può affermare che esso usa al massimo k+1 colori:

In precedenza, tramite l'algoritmo greedy si era calcolata la colorazione del grafo soprariportato, la quale usava 4 colori. Osservando il grafo ci si accorge che esso è connesso, non completo e non regolare, quindi per il teorema di Brooks, esso

Matematica Discreta 74

alla mappa è K4, quindi il suo numero cromatico è proprio pari al numero di vertici, ovvero 4.

Ricapitolando: alla mappa geografica può essere associato un grafo.