4.2 Il problema della colorazione dei vertici¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 4 · Capitolo 4: Problemi di colorazione · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di colorazione · App: Colorazione: greedy e DSATUR
Definizione 4.3: problema della colorazione dei vertici
Dato:
-
un grafo semplice \(G = (V,E)\), dove
\[ V = \{1,2,\dots,n\} \]è l'insieme degli \(n\) vertici e
\[ E \subseteq \big\{\, \{u,v\} : u,v \in V,~ u \neq v \,\big\} \]è l'insieme degli \(m\) lati,
il problema della colorazione dei vertici (VCP) chiede di decidere come assegnare un colore a ogni vertice, in modo che due vertici adiacenti non abbiano lo stesso colore e il numero totale di colori usati sia minimo.
-
Un'istanza del VCP è specificata da:
-
due numeri interi:
-
il numero di vertici \(n \in \Z_{\ge 1}\),
-
il numero di lati \(m \in \Z_{\ge 1}\),
-
-
due vettori di numeri interi di lunghezza \(m\):
-
\(\vet{u} \in \Z_{\ge 1}^m\), che contiene il primo estremo dei lati,
-
\(\vet{v} \in \Z_{\ge 1}^m\), che contiene il secondo estremo dei lati.
-
-
-
Una soluzione ammissibile del VCP è una famiglia di classi di colore, ossia sottoinsiemi di vertici ciascuno assegnato a un colore,
\[ \mathcal{Q} \subseteq 2^{V} \]tale che:
-
(i) \(\mathcal{Q}\) forma una partizione di \(V\) in classi di colore non vuote, ossia
\[ \begin{gathered} Q\neq \emptyset, \quad \text{per ogni } Q\in\mathcal{Q},\\ Q\cap Q'=\emptyset, \quad \text{per ogni } Q,Q'\in\mathcal{Q}\ \text{con } Q\neq Q',\\ \bigcup_{Q\in\mathcal{Q}} Q=V; \end{gathered} \] -
(ii) ogni classe di colore in \(\mathcal{Q}\) è un insieme stabile, ossia
\[ \{u,v\}\notin E, \quad \text{per ogni } Q\in\mathcal{Q},\ \text{per ogni } u,v\in Q\ \text{con } u\neq v. \]
Di conseguenza, il VCP si può enunciare in modo equivalente come il problema di determinare una partizione dell'insieme dei vertici in classi di colore tale che ogni classe di colore sia un insieme stabile (ossia i suoi vertici possano ricevere lo stesso colore) e il numero di classi di colore (colori) sia minimo.
-
Data un'istanza del VCP, il VCP si può enunciare formalmente come:
- Il valore ottimo del VCP è il numero cromatico \(\chi(G)\) del grafo: il numero minimo di colori (insiemi stabili) necessari per colorare tutti i vertici. Le classi di colore di una soluzione sono insiemi stabili, e il numero di classi è il numero di colori usati.
Esempio 4.1: istanza del VCP: un triangolo
Consideriamo il seguente grafo \(G = (V,E)\) con \(3\) vertici (\(n=3\)) e \(3\) lati (\(m=3\)):
L'insieme dei vertici \(V\) e l'insieme dei lati \(E\) sono:
Chiamiamo questa istanza del VCP Esempio 4.1.
Esempio 4.2: istanza del VCP: il grafo di Petersen
Consideriamo ora il seguente grafo \(G = (V,E)\) con \(10\) vertici (\(n=10\)) e \(15\) lati (\(m=15\)):
L'insieme dei vertici \(V\) e l'insieme dei lati \(E\) sono:
Chiamiamo questa istanza del VCP Esempio 4.2: è l'istanza di riferimento del capitolo.
4.2.1 Ipotesi¶
-
Facciamo le seguenti ipotesi:
-
Il grafo non ha vertici isolati. Un vertice isolato può ricevere un qualunque colore usato dal resto del grafo; se il grafo non ha lati, il valore ottimo è uno. Formalmente:
\[ \deg(v) \ge 1, \qquad \forall\, v \in V. \] -
Nessun vertice ha l'intorno contenuto nell'intorno di un altro vertice. Formalmente:
\[ N(u) \not\subseteq N(v), \qquad \forall\, u,v \in V,~ u \neq v. \]
-
-
La seconda ipotesi si può fare senza perdita di generalità, perché:
-
se \(N(u) \subseteq N(v)\), il vertice \(u\) si può eliminare senza cambiare il numero cromatico: ogni colorazione di \(G \setminus \{u\}\) si estende a \(u\) con il colore di \(v\);
-
i vertici \(u\) e \(v\) non sono adiacenti: altrimenti \(v \in N(u) \subseteq N(v)\), il che è impossibile in un grafo semplice, quindi \(u\) e \(v\) possono condividere un colore.
-
4.2.2 Due bound semplici¶
Osservazione 4.4: bound di clique
Per ogni grafo \(G = (V,E)\) abbiamo
Dimostrazione
Poiché tutti i vertici di una clique sono a due a due adiacenti, devono ricevere colori diversi in ogni soluzione ammissibile del VCP. Quindi servono almeno \(\omega(G)\) colori diversi per colorare i vertici di una clique massima, da cui \(\omega(G) \le \chi(G)\). □
Osservazione 4.5: bound degli insiemi stabili
Per ogni grafo \(G = (V,E)\) abbiamo
Dimostrazione
In una soluzione ammissibile con \(k\) classi di colore, ogni classe è un insieme stabile, quindi ha al più \(\alpha(G)\) vertici. Gli \(n\) vertici sono coperti dalle classi, quindi \(n \le k \, \alpha(G)\). Il numero \(k\) è intero, quindi \(k \ge \lceil n/\alpha(G) \rceil\). □
- Il bound di clique è utile quando il grafo ha una clique grande, e il bound degli insiemi stabili quando i suoi insiemi stabili sono piccoli. Entrambi sono bound duali: una clique e un insieme stabile si trovano senza conoscere \(\chi(G)\).
4.2.3 Contare le soluzioni, una prima soluzione e i bound¶
-
Soluzioni candidate. Le soluzioni candidate sono le partizioni di \(V\), contate dai numeri di Bell (Capitolo 1 «Problemi di ottimizzazione combinatoria»). Per l'Esempio 4.1 abbiamo \(B(3) = 5\) partizioni e una sola è ammissibile: tre singoletti, poiché ogni coppia di vertici è adiacente. Quindi \(\chi(G) = 3\).
-
Per l'Esempio 4.2 abbiamo \(B(10) = 115\,975\) partizioni, e \(7\,430\) di esse sono ammissibili, cioè hanno come classi solo insiemi stabili.
-
Una prima soluzione, a occhio. La colorazione mostrata nell'Esempio 4.2 usa \(3\) colori:
\[ \mathcal{Q} = \big\{\, \{1,4,7,8\},~ \{2,5,6\},~ \{3,9,10\} \,\big\}. \]Nessun lato unisce due vertici della stessa classe, quindi è ammissibile: è un bound primale, \(\UB = 3 \ge \chi(G)\).
-
Bound duali sul grafo di Petersen. Il grafo non ha triangoli, quindi \(\omega(G) = 2\) e il bound di clique dà solo \(\LB = 2\): resta un gap di \(1\).
-
I vertici \(1,2,3,4,5\) formano un ciclo con \(5\) vertici, e così \(6,7,8,9,10\) (i lati della figura). Un insieme stabile contiene al più \(2\) vertici di ogni ciclo, quindi \(\alpha(G) \le 4\); l'insieme \(\{1,4,7,8\}\) mostra che \(\alpha(G) = 4\).
-
Il bound degli insiemi stabili dà \(\lceil 10/4 \rceil = 3\). I due bound coincidono: il gap è nullo e \(\chi(G) = 3\).
4.3 Osservazioni¶
-
Brooks (1941) dimostrò che un grafo connesso che non è né completo né un ciclo dispari si può colorare con al più \(\Delta\) colori, dove \(\Delta\) è il grado massimo.
-
Karp (1972) incluse il numero cromatico fra i suoi \(21\) problemi NP-completi. Garey, Johnson e Stockmeyer (1976) dimostrarono che stabilire se \(3\) colori bastano resta NP-completo sui grafi planari di grado massimo \(4\).
4.4 Errori tipici¶
Attenzione
-
Confondere una clique con un insieme stabile. In una clique tutte le coppie sono lati e i vertici richiedono colori diversi; in un insieme stabile nessuna coppia è un lato e i vertici possono condividere un colore.
-
Credere che il bound di clique sia stretto. Non lo è: il grafo di Petersen ha \(\omega(G) = 2\) e \(\chi(G) = 3\), e lo stesso accade per un ciclo con \(5\) vertici.
-
Contare le permutazioni dei colori come soluzioni diverse. Una soluzione è una partizione dei vertici in insiemi stabili: scambiare i nomi di due colori dà la stessa soluzione.
-
Usare una classe che non è un insieme stabile. Una classe di colore con due vertici adiacenti rende la soluzione inammissibile, qualunque sia il numero di colori.
-
Dimenticare le ipotesi. Un vertice isolato e un vertice con \(N(u) \subseteq N(v)\) si possono eliminare prima di risolvere, senza cambiare il numero cromatico.
4.5 In sintesi¶
In sintesi
-
Il VCP partiziona i vertici di un grafo nel numero minimo di insiemi stabili; il valore ottimo è il numero cromatico \(\chi(G)\).
-
Una clique richiede colori diversi e un insieme stabile può condividerne uno; le clique di \(G\) sono gli insiemi stabili del grafo complementare.
-
Una colorazione trovata a occhio è un bound primale; il bound di clique \(\omega(G)\) e il bound degli insiemi stabili \(\lceil n/\alpha(G) \rceil\) sono bound duali.
-
I bound non sempre si incontrano: sul grafo di Petersen il bound di clique lascia un gap, il bound degli insiemi stabili lo chiude.
Quadro riassuntivo delle istanze di riferimento.
| istanza (min) | lower bound | upper bound | da |
|---|---|---|---|
| Esempio 4.1 (triangolo) | \(3\) (bound di clique) | \(3\) (a occhio) | questo capitolo |
| Esempio 4.2 (Petersen) | \(3\) (bound degli insiemi stabili) | \(3\) (a occhio) | questo capitolo |
Esercizi su questo capitolo: Problemi di colorazione
Approfondimento: che cosa fa il corso su questo problema