30.8 Colorazione dei vertici: greedy e DSATUR

Parte 4 · Algoritmi euristici · Capitolo 30 · Capitolo 30: Euristiche costruttive · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Euristiche costruttive · App: Euristiche per il bin packing · App: List scheduling e LPT · App: Colorazione: greedy e DSATUR · App: TSP: nearest neighbour e 2-opt

• Il problema di questa sezione è il problema della colorazione dei vertici (VCP): la sua definizione e le sue ipotesi sono nella sua pagina. Il grafo è \(G=(V,E)\), e il valore ottimo è il numero cromatico \(\chi(G)\).

30.8.1 La colorazione greedy

Il Greedy Coloring Algorithm (indicato con \(GC\)) è un'euristica costruttiva per il VCP. I colori sono gli interi \(1,2,3,\dots\); l'algoritmo esamina i vertici nell'ordine di una lista data \(\lambda\) e dà a ogni vertice il colore minimo non usato dai suoi vicini già colorati.

Algoritmo: Colorazione greedy

Input: istanza del VCP \(G=(V,E)\) con \(n\) vertici; lista \(\lambda[1..n]\)

Output: assegnamento vertici-colori \(col[1..n]\) e numero di colori \(nc\)

1Function GreedyColoring(\(n, E, \lambda\))

2\(col := \text{nuovo vettore}[1..n]\), con tutte le componenti \(0\) ▹ \(0\) = non ancora colorato

3for \(k := 1\) to \(n\) do

4\(v := \lambda[k]\)

5\(U := \{\, col[u] : u \in N(v),\ col[u] \neq 0 \,\}\) \(col[v] \leftarrow \min\{\, c\in\Z_{\ge1} : c \notin U \,\}\) ▹ colori dei vicini colorati colore libero minimo

6end

7return \(col\), \(nc = \max_v col[v]\)

Esegui in Colab:PythonC++

• Le classi di colore \(Q_c=\{v : col[v]=c\}\) sono insiemi stabili per costruzione, quindi \(GC\) restituisce sempre una colorazione ammissibile. Richiede tempo \(O(n+|E|)\).

• Come \(LIST\), \(GC\) dipende dall'ordine della lista, e l'ordine può fare una grande differenza.

Esempio 30.12: \(GC\) sul grafo di Petersen, due ordini

Lista \(\lambda=(1,2,\dots,10)\). I colori dei vicini colorati \(U\) e il colore assegnato sono:

\[ \begin{array}{c|cccccccccc} \hline {v} & {1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} & {9} & {10} \\ \hline {U} & {\emptyset} & {\{1\}} & {\{2\}} & {\{1\}} & {\{1,2\}} & {\{1\}} & {\{2\}} & {\{1,2\}} & {\{1,2\}} & {\{1,3\}} \\ {col[v]} & {1} & {2} & {1} & {2} & {3} & {2} & {1} & {3} & {3} & {2} \\ \hline \end{array} \]

\(GC\) usa \(3\) colori (rosso \(=1\), blu \(=2\), giallo \(=3\) nella figura). Il \(5\)-ciclo esterno \(1,2,3,4,5\) è un ciclo dispari e richiede \(3\) colori, quindi \(\chi(G)=3\) e questa colorazione è ottima.

Lista \(\lambda=(1,2,3,4,5,7,8,6,9,10)\). I primi cinque vertici ricevono gli stessi colori di prima; poi

\[ \begin{array}{c|ccccc} \hline {v} & {7} & {8} & {6} & {9} & {10} \\ \hline {U} & {\{2\}} & {\{1\}} & {\{1,2\}} & {\{1,2,3\}} & {\{1,2,3\}} \\ {col[v]} & {1} & {2} & {3} & {4} & {4} \\ \hline \end{array} \]

e \(GC\) usa \(4\) colori: il vertice \(8\) prende il colore \(2\), che il primo ordine dava al vertice \(6\), e i vertici \(9\) e \(10\) vedono allora tutti e tre i colori fra i loro vicini.

30.8.2 DSATUR

Il DSATUR Algorithm (Degree of SATURation, indicato con \(DSATUR\)) è un'euristica costruttiva per il VCP. Non usa una lista fissa: a ogni passo colora, con il colore libero minimo, un vertice non colorato di grado di saturazione massimo, cioè con il maggior numero di colori diversi fra i suoi vicini; i pareggi si risolvono con il grado massimo nel sottografo dei vertici non colorati, e poi con l'indice minimo.

Algoritmo: DSATUR

Input: istanza del VCP \(G=(V,E)\) con \(n\) vertici

Output: assegnamento vertici-colori \(col[1..n]\) e numero di colori \(nc\)

1Function DSATUR(\(n, E\))

2\(col := \text{nuovo vettore}[1..n]\), con tutte le componenti \(0\)

3for \(k := 1\) to \(n\) do

4for ogni \(u\) non colorato do

5\(sat[u] \leftarrow |\{\, col[w] : w\in N(u),\ col[w]\neq0 \,\}|\) \(du[u] \leftarrow |\{\, w\in N(u) : col[w]=0 \,\}|\) ▹ grado di saturazione grado fra i non colorati

6end

7\(v :=\) il vertice non colorato che massimizza \((sat[v], du[v])\) in ordine lessicografico (indice minimo)

8\(col[v] \leftarrow \min\{\, c\in\Z_{\ge1} : c \neq col[w]~\forall w\in N(v) \,\}\)

9end

10return \(col\), \(nc = \max_v col[v]\)

• Perché il grado di saturazione. Un vertice con molti colori diversi intorno ha pochi colori rimasti: se lo rimandiamo, può restare senza nessuno dei colori già in uso. \(DSATUR\) colora prima i vertici più vincolati, la stessa idea di “prima gli oggetti più difficili” di FFD e \(LPT\), ma aggiornata dinamicamente dopo ogni assegnamento.

• \(DSATUR\) è \(GC\) con una lista costruita al volo, quindi ogni proprietà di \(GC\) che vale per ogni lista vale anche per \(DSATUR\). Un'implementazione diretta richiede tempo \(O(n^2)\).

Esempio 30.13: \(DSATUR\) sul grafo di Petersen

Tutti i vertici hanno grado \(3\). Il vertice scelto a ogni passo, il suo grado di saturazione, il suo grado fra i vertici non colorati e il suo colore sono:

passo	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)
\(v\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(8\)	\(7\)	\(9\)	\(10\)
\(sat[v]\)	\(0\)	\(1\)	\(1\)	\(1\)	\(2\)	\(1\)	\(2\)	\(1\)	\(2\)	\(2\)
\(du[v]\)	\(3\)	\(2\)	\(2\)	\(2\)	\(1\)	\(2\)	\(1\)	\(2\)	\(0\)	\(0\)
\(col[v]\)	\(1\)	\(2\)	\(1\)	\(2\)	\(3\)	\(2\)	\(3\)	\(1\)	\(3\)	\(2\)

Al passo \(1\) tutti i vertici sono in pareggio e si sceglie il vertice \(1\). Al passo \(2\) i vertici \(2\), \(5\), \(6\) hanno grado di saturazione \(1\) e due vicini non colorati ciascuno: si sceglie l'indice minimo, \(2\). Al passo \(7\) il vertice \(8\) (vicini \(3\) e \(6\), colori \(1\) e \(2\)) ha grado di saturazione \(2\) e passa prima del vertice \(7\). \(DSATUR\) usa \(3=\chi(G)\) colori, la stessa colorazione di \(GC\) con la lista \((1,2,\dots,10)\).

30.8.3 Che cosa garantisce la colorazione greedy

Proposizione 30.5

Per ogni grafo \(G\) e ogni lista \(\lambda\),

\[ GC(I) \;\le\; \Delta(G)+1 . \]

Dimostrazione

Quando si colora il vertice \(v\), l'insieme \(U\) dei colori dei suoi vicini colorati ha al più \(\deg(v)\le\Delta(G)\) elementi, quindi uno dei colori \(1,2,\dots,\Delta(G)+1\) non è in \(U\), e il colore libero minimo è al più \(\Delta(G)+1\). □

• Il bound vale anche per \(DSATUR\), che è \(GC\) con una lista particolare, ed è raggiunto dai grafi completi (\(\Delta=n-1\), \(\chi=n\)) e dai cicli dispari (\(\Delta=2\), \(\chi=3\)), qualunque sia la lista.

• Non è una garanzia di prestazione: confronta \(GC(I)\) con \(\Delta(G)+1\), non con \(\chi(G)\), e \(\Delta(G)+1\) può essere molto più grande di \(\chi(G)\). La prossima proposizione mostra che una cattiva lista può davvero imporre così tanti colori a un grafo che ne richiede solo due.

• D'altra parte, qualche lista è sempre ottima: se \(Q_1,\dots,Q_{\chi(G)}\) sono le classi di colore di una colorazione ottima, \(GC\) con prima i vertici di \(Q_1\), poi quelli di \(Q_2\), e così via, dà a ogni vertice di \(Q_c\) un colore al più \(c\), quindi usa al più \(\chi(G)\) colori. La difficoltà sta tutta nel trovare la lista.

Proposizione 30.6

Per ogni \(k\ge3\) esistono un grafo \(G_k\) con \(n=2k\) vertici, \(\chi(G_k)=2\) e \(\Delta(G_k)=k-1\), e una lista \(\lambda\), tali che

\[ GC(I_k) \;=\; k \;=\; \frac{n}{2} . \]

Dimostrazione

\(G_k\) è il grafo corona: i vertici sono \(u_1,\dots,u_k\) e \(v_1,\dots,v_k\), e \(u_i\) è adiacente a \(v_j\) se e solo se \(i\neq j\) (il grafo bipartito completo \(K_{k,k}\) privato di un matching perfetto). È bipartito, con almeno un arco, quindi \(\chi(G_k)=2\); ogni vertice ha grado \(k-1\). La lista è \(\lambda=(u_1,v_1,u_2,v_2,\dots,u_k,v_k)\).

Mostriamo per induzione su \(i\) che \(GC\) dà il colore \(i\) sia a \(u_i\) sia a \(v_i\). Per \(i=1\) nessun vicino è colorato quando si esamina \(u_1\), e \(v_1\) non è adiacente a \(u_1\): entrambi ricevono il colore \(1\). Quando si esamina \(u_i\), i suoi vicini colorati sono \(v_1,\dots,v_{i-1}\), con colori \(1,\dots,i-1\) per induzione, quindi \(u_i\) riceve il colore \(i\); quando si esamina \(v_i\), i suoi vicini colorati sono \(u_1,\dots,u_{i-1}\) (\(u_i\) non è un vicino), con colori \(1,\dots,i-1\), quindi anche \(v_i\) riceve il colore \(i\). Quindi \(GC(I_k)=k\). □

• Sui grafi corona \(\frac{GC(I_k)}{\chi(G_k)}=\frac{k}{2}=\frac{n}{4}\), che cresce senza limite: con una lista arbitraria, \(GC\) non ha una garanzia di prestazione costante. La lista \((u_1,\dots,u_k,v_1,\dots,v_k)\), prima le classi di colore, dà \(2\) colori.

• I grafi corona soddisfano le ipotesi del VCP per \(k\ge3\): nessun vertice isolato, e \(N(u_i)=\{v_j:j\neq i\}\) non è contenuto in \(N(u_{i'})\) né in alcun \(N(v_j)\subseteq\{u_1,\dots,u_k\}\).

Esempio 30.14: \(GC\) e \(DSATUR\) sul grafo corona \(G_4\)

Numeriamo i vertici \(u_i=2i-1\) e \(v_i=2i\), così che \(u_1,v_1,\dots,u_4,v_4\) siano \(1,2,\dots,8\), e \(E=\{\{2i-1,2j\}: i\neq j\}\), con \(12\) archi.

Con la lista \((1,2,\dots,8)=(u_1,v_1,\dots,u_4,v_4)\), \(GC\) usa \(4\) colori, uno per ogni coppia \(\{u_i,v_i\}\) (come in figura); con la lista \((1,3,5,7,2,4,6,8)\) usa \(2\) colori.

\(DSATUR\) sceglie il vertice \(1\) (\(u_1\), colore \(1\)), poi i vertici \(4\), \(5\), \(2\), \(3\), \(6\), \(7\), \(8\), con colori \(2,1,2,1,2,1,2\): i vertici \(u_i\) ricevono il colore \(1\) e i vertici \(v_i\) il colore \(2\), e \(DSATUR\) usa \(2=\chi(G_4)\) colori. Dopo il primo passo, ogni vertice adiacente a un vertice colorato ha grado di saturazione \(1\), e il vertice scelto sta sempre dal lato opposto all'ultimo colorato.

30.8.4 DSATUR come euristica

• Sui grafi bipartiti \(DSATUR\) usa sempre al più \(2\) colori, come sui grafi corona; questo è dimostrato nell'articolo che lo ha introdotto (Brélaz, 1979).

• Sui grafi generali \(DSATUR\) non ha una garanzia di prestazione, poiché il VCP non è approssimabile. È comunque una delle euristiche costruttive più usate per il VCP, perché sulla maggior parte dei grafi usa pochi colori in più di \(\chi(G)\), spesso nessuno; è anche la base di algoritmi esatti di branch-and-bound per il VCP, che fanno branching sul vertice scelto dalla regola di \(DSATUR\).

---

Avanti: 30.9 Costruzione randomizzata