Esercizi · Colorazione dei vertici: il branch-and-bound DSATUR¶

Esercizi · Capitolo 42 · ogni soluzione si apre con un clic · Capitolo 42: Colorazione dei vertici (VCP) · Eserciziario, volume 6 (PDF)

Regole usate in questi esercizi

L'algoritmo di branch-and-bound DSATUR del capitolo «Colorazione dei vertici: il branch-and-bound DSATUR». In un nodo $k$, con $q(k)$ colori usati, vertici colorati $V^k$ e vertici non colorati $U^k$:

\[\begin{equation*} \begin{gathered} \mathit{sat}_k(v)=\big|\{\mathit{col}^k(u): u\in N(v)\cap V^k\}\big|, \qquad \mathit{du}_k(v)=|N(v)\cap U^k|,\\ F_k(v)=\{\, c\le q(k): \text{nessun vicino di $v$ ha colore $c$} \,\}. \end{gathered} \tag{D1} \end{equation*}\]

(D2) Bound. $\UB$ = colori dell'euristica $DSATUR$; $K$ = clique greedy (vertici per grado non crescente, pareggi con l'indice minimo; un vertice entra se è adiacente a tutti i vertici di $K$), $\LB=|K|$, e il vertice di $K$ in posizione $i$ è pre-colorato con il colore $i$.
(D3) Branching. Il vertice $v\in U^k$ con $\mathit{sat}_k(v)$ massimo, poi $\mathit{du}_k(v)$ massimo, poi indice minimo; un figlio per ogni $c\in F_k(v)$ e uno per il colore nuovo $q(k)+1$, in ordine crescente di colore.
(D4) Potatura. Un nodo con $q\ge\UB$ è potato per bound. Una colorazione completa con $q<\UB$ è una nuova soluzione incumbent: $\UB\leftarrow q$, i nodi della lista con $q\ge\UB$ vengono rimossi, e l'algoritmo si ferma se $\UB=\LB$.
(D5) Visita. In profondità: la lista è una pila e il figlio con il colore minimo si estrae per primo; i nodi sono numerati nell'ordine di valutazione.

Esercizio 42.1: Il nodo radice del branch-and-bound DSATUR (P1)

Consideriamo due grafi. Il grafo $G_a$ di un calendario d'esami, con $V=\{1,\dots,6\}$ e gli spigoli

\[ E_a=\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{3,5\},\{4,5\},\{4,6\},\{5,6\}\}, \]

e il ciclo $G_b=C_5$, con $V=\{1,\dots,5\}$ e gli spigoli

\[ E_b=\{\{1,2\},\{1,5\},\{2,3\},\{3,4\},\{4,5\}\}. \]

Figura 1

Domande

Eseguire l'euristica $DSATUR$ su $G_a$ e dare l'upper bound $\UB$.
Trovare la clique greedy di $G_a$ e il lower bound $\LB$, e stabilire se l'algoritmo di branch-and-bound DSATUR fa branching.
Rispondere alle stesse due domande per $G_b$.
Per $G_b$, scrivere il nodo radice ed eseguire la prima iterazione dell'algoritmo: il vertice di branching, i suoi colori ammissibili e i figli.

Soluzione

Usiamo le regole (D1)–(D5) del riquadro all'inizio del capitolo.

I passi di $DSATUR$ su $G_a$ sono:

passo	$1$	$2$	$3$	$4$	$5$	$6$
$v$	$2$	$3$	$1$	$4$	$5$	$6$
$\mathit{sat}(v)$	$0$	$1$	$2$	$1$	$1$	$2$
$\mathit{du}(v)$	$3$	$2$	$0$	$2$	$1$	$0$
$\mathit{col}(v)$	$1$	$2$	$3$	$2$	$1$	$3$

Al passo $3$ il vertice $1$ vede i colori $1$ e $2$, quindi è scelto prima dei vertici con $\mathit{sat}=1$. $DSATUR$ dà $\big\{\{2,5\},~\{3,4\},~\{1,6\}\big\}$, quindi $\UB=3$.

I gradi sono $\deg(1)=2$, $\deg(2)=3$, $\deg(3)=3$, $\deg(4)=3$, $\deg(5)=3$, $\deg(6)=2$, quindi i vertici si scorrono nell'ordine $2,3,4,5,1,6$. Entrano i vertici $2,3,1$, in quest'ordine; a ogni altro vertice manca uno spigolo verso un vertice già in $K$. Quindi $K=\{1,2,3\}$ (nell'ordine di ingresso: $k_1=2$, $k_2=3$, $k_3=1$) e $\LB=3$. Poiché $\LB=\UB=3$, la colorazione di $DSATUR$ è ottima e l'algoritmo si ferma al Passo 0, senza branching: $\chi(G_a)=3$.

I passi di $DSATUR$ su $G_b$ sono:

passo	$1$	$2$	$3$	$4$	$5$
$v$	$1$	$2$	$3$	$4$	$5$
$\mathit{sat}(v)$	$0$	$1$	$1$	$1$	$2$
$\mathit{du}(v)$	$2$	$1$	$1$	$1$	$0$
$\mathit{col}(v)$	$1$	$2$	$1$	$2$	$3$

$DSATUR$ dà $\big\{\{1,3\},~\{2,4\},~\{5\}\big\}$, quindi $\UB=3$. Tutti i gradi sono uguali, quindi i vertici si scorrono nell'ordine $1,2,3,4,5$. Entrano i vertici $1,2$, in quest'ordine; a ogni altro vertice manca uno spigolo verso un vertice già in $K$. Quindi $K=\{1,2\}$ (nell'ordine di ingresso: $k_1=1$, $k_2=2$) e $\LB=2$. Ora $\LB=2<3=\UB$: l'algoritmo fa branching.

Il nodo $1$ colora $\mathit{col}^1(1)=1$, $\mathit{col}^1(2)=2$, con $q(1)=2$. I vertici $3,5$ hanno $\mathit{sat}=1$ e lo stesso $\mathit{du}=1$: vince l'indice minimo, e il vertice di branching è $3$. Il suo vicino $2$ ha colore $2$, quindi $F_1(3)=\{1\}$.
- Nodo $2$: $\mathit{col}(3)=1$, con $q(2)=2<\UB=3$: il nodo sopravvive.
- Nodo $3$: $\mathit{col}(3)=3$, il colore nuovo, con $q(3)=3\ge\UB=3$: potato per bound.
La ricerca continua dal nodo $2$: è la stessa ricerca fatta sul ciclo esterno del grafo di Petersen, e termina con $6$ nodi e $\chi(G_b)=3$.

Su $G_a$ la clique $\{2,3,1\}$ raggiunge il bound di $DSATUR$: niente branching. Su $G_b$ il bound della clique è $2$ e l'albero serve per dimostrare $\chi(C_5)=3$.

Esercizio 42.2: Dimostrare un lower bound: la ruota $W_5$ (P2)

Consideriamo la ruota $W_5$ (un ciclo su $1,\dots,5$ e il mozzo $6$), il grafo $G=(V,E)$ con $V=\{1,\dots,6\}$ e gli spigoli

\[ E=\{\{1,2\},\{1,5\},\{1,6\},\{2,3\},\{2,6\},\{3,4\},\{3,6\},\{4,5\},\{4,6\},\{5,6\}\}, \]

disegnato qui sotto:

Figura 2

Domande

Eseguire l'euristica $DSATUR$: dare l'ordine dei vertici, la colorazione e l'upper bound $\UB$.
Trovare la clique greedy $K$, il lower bound $\LB$ e il nodo radice dell'algoritmo di branch-and-bound DSATUR.
Eseguire l'algoritmo di branch-and-bound DSATUR, iterazione per iterazione.
Disegnare l'albero di branch-and-bound e dare il numero cromatico di $G$ con una colorazione ottima.

Soluzione

Usiamo le regole (D1)–(D5) del riquadro all'inizio del capitolo.

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$
$v$	$6$	$1$	$2$	$3$	$4$	$5$
$\mathit{sat}(v)$	$0$	$1$	$2$	$2$	$2$	$3$
$\mathit{du}(v)$	$5$	$2$	$1$	$1$	$1$	$0$
$\mathit{col}(v)$	$1$	$2$	$3$	$2$	$3$	$4$

$DSATUR$ dà $\big\{\{6\},~\{1,3\},~\{2,4\},~\{5\}\big\}$, quindi $\UB=4$.

I gradi sono $\deg(1)=3$, $\deg(2)=3$, $\deg(3)=3$, $\deg(4)=3$, $\deg(5)=3$, $\deg(6)=5$, quindi i vertici si scorrono nell'ordine $6,1,2,3,4,5$. Entrano i vertici $6,1,2$, in quest'ordine; a ogni altro vertice manca uno spigolo verso un vertice già in $K$. Quindi $K=\{1,2,6\}$ (nell'ordine di ingresso: $k_1=6$, $k_2=1$, $k_3=2$) e $\LB=3$. Poiché $\LB=3<4=\UB$, l'algoritmo fa branching. Il nodo $1$ colora $\mathit{col}^1(6)=1$, $\mathit{col}^1(1)=2$, $\mathit{col}^1(2)=3$, con $q(1)=3$:
**Iterazione 1**
Il nodo $1$ viene estratto dalla lista, con $Q_1=\{6\}$, $Q_2=\{1\}$, $Q_3=\{2\}$ e $q(1)=3$. I vertici $3,5$ hanno $\mathit{sat}=2$ e lo stesso $\mathit{du}=1$: vince l'indice minimo, e il vertice di branching è $3$. I suoi colori ammissibili sono $F_{1}(3)=\{2\}$.
- Nodo $2$: $\mathit{col}(3)=2$, con $q(2)=3<\UB=4$: il nodo sopravvive.
- Nodo $3$: $\mathit{col}(3)=4$, il colore nuovo, con $q(3)=4\ge\UB=4$: potato per bound.
**Iterazione 2**
Il nodo $2$ viene estratto dalla lista, con $Q_1=\{6\}$, $Q_2=\{1,3\}$, $Q_3=\{2\}$ e $q(2)=3$. I vertici $4,5$ hanno $\mathit{sat}=2$ e lo stesso $\mathit{du}=1$: vince l'indice minimo, e il vertice di branching è $4$. I suoi colori ammissibili sono $F_{2}(4)=\{3\}$.
- Nodo $4$: $\mathit{col}(4)=3$, con $q(4)=3<\UB=4$: il nodo sopravvive.
- Nodo $5$: $\mathit{col}(4)=4$, il colore nuovo, con $q(5)=4\ge\UB=4$: potato per bound.
**Iterazione 3**
Il nodo $4$ viene estratto dalla lista, con $Q_1=\{6\}$, $Q_2=\{1,3\}$, $Q_3=\{2,4\}$ e $q(4)=3$. Il vertice $5$ è l'unico con $\mathit{sat}=3$: è il vertice di branching. I suoi colori ammissibili sono $F_{4}(5)=\emptyset$.
- Nodo $6$: $\mathit{col}(5)=4$, il colore nuovo, con $q(6)=4\ge\UB=4$: potato per bound.
Terminazione La lista è vuota: la soluzione incumbent di $DSATUR$ è ottima.

L'albero ha $6$ nodi; i nodi potati sono tratteggiati.

Figura 4

Nodo	Padre	Figlio	$q$	$\UB$	Vertice di branching	Esito
$1$	–	radice	$3$	$4$	$3$	branching
$2$	$1$	$\mathit{col}(3)=2$	$3$	$4$	$4$	branching
$3$	$1$	$\mathit{col}(3)=4$	$4$	$4$	–	potato per bound
$4$	$2$	$\mathit{col}(4)=3$	$3$	$4$	$5$	branching
$5$	$2$	$\mathit{col}(4)=4$	$4$	$4$	–	potato per bound
$6$	$4$	$\mathit{col}(5)=4$	$4$	$4$	–	potato per bound

Quindi $\chi(G)=4$, con la colorazione ottima $\big\{\{6\},~\{1,3\},~\{2,4\},~\{5\}\big\}$:

Figura 5

Il bound della clique dà solo $3$: l'albero dimostra che il ciclo dispari e il mozzo richiedono un quarto colore.

Esercizio 42.3: Il complemento del ciclo $C_7$ (P3)

Consideriamo il complemento del ciclo $C_7$ (due vertici sono adiacenti se non sono consecutivi sul ciclo $1,2,\dots,7$), il grafo $G=(V,E)$ con $V=\{1,\dots,7\}$ e gli spigoli

\[ \begin{aligned} E=\{&\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{2,4\},\{2,5\},\{2,6\},\\ &\{2,7\},\{3,5\},\{3,6\},\{3,7\},\{4,6\},\{4,7\},\{5,7\}\}, \end{aligned} \]

disegnato qui sotto:

Figura 6

Domande

Eseguire l'euristica $DSATUR$: dare l'ordine dei vertici, la colorazione e l'upper bound $\UB$.
Trovare la clique greedy $K$, il lower bound $\LB$ e il nodo radice dell'algoritmo di branch-and-bound DSATUR.
Eseguire l'algoritmo di branch-and-bound DSATUR, iterazione per iterazione.
Disegnare l'albero di branch-and-bound e dare il numero cromatico di $G$ con una colorazione ottima.

Soluzione

Usiamo le regole (D1)–(D5) del riquadro all'inizio del capitolo.

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$
$v$	$1$	$3$	$5$	$6$	$4$	$2$	$7$
$\mathit{sat}(v)$	$0$	$1$	$2$	$2$	$2$	$2$	$3$
$\mathit{du}(v)$	$4$	$3$	$2$	$2$	$2$	$1$	$0$
$\mathit{col}(v)$	$1$	$2$	$3$	$3$	$2$	$1$	$4$

$DSATUR$ dà $\big\{\{1,2\},~\{3,4\},~\{5,6\},~\{7\}\big\}$, quindi $\UB=4$.

Tutti i gradi sono uguali, quindi i vertici si scorrono nell'ordine $1,2,3,4,5,6,7$. Entrano i vertici $1,3,5$, in quest'ordine; a ogni altro vertice manca uno spigolo verso un vertice già in $K$. Quindi $K=\{1,3,5\}$ (nell'ordine di ingresso: $k_1=1$, $k_2=3$, $k_3=5$) e $\LB=3$. Poiché $\LB=3<4=\UB$, l'algoritmo fa branching. Il nodo $1$ colora $\mathit{col}^1(1)=1$, $\mathit{col}^1(3)=2$, $\mathit{col}^1(5)=3$, con $q(1)=3$:
**Iterazione 1**
Il nodo $1$ viene estratto dalla lista, con $Q_1=\{1\}$, $Q_2=\{3\}$, $Q_3=\{5\}$ e $q(1)=3$. I vertici $6,7$ hanno $\mathit{sat}=2$ e lo stesso $\mathit{du}=2$: vince l'indice minimo, e il vertice di branching è $6$. I suoi colori ammissibili sono $F_{1}(6)=\{3\}$.
- Nodo $2$: $\mathit{col}(6)=3$, con $q(2)=3<\UB=4$: il nodo sopravvive.
- Nodo $3$: $\mathit{col}(6)=4$, il colore nuovo, con $q(3)=4\ge\UB=4$: potato per bound.
**Iterazione 2**
Il nodo $2$ viene estratto dalla lista, con $Q_1=\{1\}$, $Q_2=\{3\}$, $Q_3=\{5,6\}$ e $q(2)=3$. I vertici $4,7$ hanno $\mathit{sat}=2$ e lo stesso $\mathit{du}=2$: vince l'indice minimo, e il vertice di branching è $4$. I suoi colori ammissibili sono $F_{2}(4)=\{2\}$.
- Nodo $4$: $\mathit{col}(4)=2$, con $q(4)=3<\UB=4$: il nodo sopravvive.
- Nodo $5$: $\mathit{col}(4)=4$, il colore nuovo, con $q(5)=4\ge\UB=4$: potato per bound.
**Iterazione 3**
Il nodo $4$ viene estratto dalla lista, con $Q_1=\{1\}$, $Q_2=\{3,4\}$, $Q_3=\{5,6\}$ e $q(4)=3$. I vertici $2,7$ hanno $\mathit{sat}=2$ e lo stesso $\mathit{du}=1$: vince l'indice minimo, e il vertice di branching è $2$. I suoi colori ammissibili sono $F_{4}(2)=\{1\}$.
- Nodo $6$: $\mathit{col}(2)=1$, con $q(6)=3<\UB=4$: il nodo sopravvive.
- Nodo $7$: $\mathit{col}(2)=4$, il colore nuovo, con $q(7)=4\ge\UB=4$: potato per bound.
**Iterazione 4**
Il nodo $6$ viene estratto dalla lista, con $Q_1=\{1,2\}$, $Q_2=\{3,4\}$, $Q_3=\{5,6\}$ e $q(6)=3$. Il vertice $7$ è l'unico con $\mathit{sat}=3$: è il vertice di branching. I suoi colori ammissibili sono $F_{6}(7)=\emptyset$.
- Nodo $8$: $\mathit{col}(7)=4$, il colore nuovo, con $q(8)=4\ge\UB=4$: potato per bound.
Terminazione La lista è vuota: la soluzione incumbent di $DSATUR$ è ottima.

L'albero ha $8$ nodi; i nodi potati sono tratteggiati.

Figura 8

Nodo	Padre	Figlio	$q$	$\UB$	Vertice di branching	Esito
$1$	–	radice	$3$	$4$	$6$	branching
$2$	$1$	$\mathit{col}(6)=3$	$3$	$4$	$4$	branching
$3$	$1$	$\mathit{col}(6)=4$	$4$	$4$	–	potato per bound
$4$	$2$	$\mathit{col}(4)=2$	$3$	$4$	$2$	branching
$5$	$2$	$\mathit{col}(4)=4$	$4$	$4$	–	potato per bound
$6$	$4$	$\mathit{col}(2)=1$	$3$	$4$	$7$	branching
$7$	$4$	$\mathit{col}(2)=4$	$4$	$4$	–	potato per bound
$8$	$6$	$\mathit{col}(7)=4$	$4$	$4$	–	potato per bound

Quindi $\chi(G)=4$, con la colorazione ottima $\big\{\{1,2\},~\{3,4\},~\{5,6\},~\{7\}\big\}$:

Figura 9

Ogni insieme stabile di $G$ ha al più $2$ vertici, quindi il bound degli insiemi stabili $\lceil 7/2\rceil=4$ del Capitolo 4 conferma il risultato.

Esercizio 42.4: Migliorare la soluzione incumbent (P4)

Consideriamo un grafo con $7$ vertici e $11$ spigoli, il grafo $G=(V,E)$ con $V=\{1,\dots,7\}$ e gli spigoli

\[ \begin{aligned} E=\{&\{1,2\},\{1,3\},\{1,4\},\{1,7\},\{2,3\},\{2,7\},\\ &\{3,6\},\{4,5\},\{4,6\},\{5,6\},\{5,7\}\}, \end{aligned} \]

disegnato qui sotto:

Figura 10

Domande

Eseguire l'euristica $DSATUR$: dare l'ordine dei vertici, la colorazione e l'upper bound $\UB$.
Trovare la clique greedy $K$, il lower bound $\LB$ e il nodo radice dell'algoritmo di branch-and-bound DSATUR.
Eseguire l'algoritmo di branch-and-bound DSATUR, iterazione per iterazione.
Disegnare l'albero di branch-and-bound e dare il numero cromatico di $G$ con una colorazione ottima.

Soluzione

Usiamo le regole (D1)–(D5) del riquadro all'inizio del capitolo.

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$
$v$	$1$	$2$	$3$	$7$	$4$	$5$	$6$
$\mathit{sat}(v)$	$0$	$1$	$2$	$2$	$1$	$2$	$3$
$\mathit{du}(v)$	$4$	$2$	$1$	$1$	$2$	$1$	$0$
$\mathit{col}(v)$	$1$	$2$	$3$	$3$	$2$	$1$	$4$

$DSATUR$ dà $\big\{\{1,5\},~\{2,4\},~\{3,7\},~\{6\}\big\}$, quindi $\UB=4$.

I gradi sono $\deg(1)=4$, $\deg(2)=3$, $\deg(3)=3$, $\deg(4)=3$, $\deg(5)=3$, $\deg(6)=3$, $\deg(7)=3$, quindi i vertici si scorrono nell'ordine $1,2,3,4,5,6,7$. Entrano i vertici $1,2,3$, in quest'ordine; a ogni altro vertice manca uno spigolo verso un vertice già in $K$. Quindi $K=\{1,2,3\}$ (nell'ordine di ingresso: $k_1=1$, $k_2=2$, $k_3=3$) e $\LB=3$. Poiché $\LB=3<4=\UB$, l'algoritmo fa branching. Il nodo $1$ colora $\mathit{col}^1(1)=1$, $\mathit{col}^1(2)=2$, $\mathit{col}^1(3)=3$, con $q(1)=3$:
**Iterazione 1**
Il nodo $1$ viene estratto dalla lista, con $Q_1=\{1\}$, $Q_2=\{2\}$, $Q_3=\{3\}$ e $q(1)=3$. Il vertice $7$ è l'unico con $\mathit{sat}=2$: è il vertice di branching. I suoi colori ammissibili sono $F_{1}(7)=\{3\}$.
- Nodo $2$: $\mathit{col}(7)=3$, con $q(2)=3<\UB=4$: il nodo sopravvive.
- Nodo $3$: $\mathit{col}(7)=4$, il colore nuovo, con $q(3)=4\ge\UB=4$: potato per bound.
**Iterazione 2**
Il nodo $2$ viene estratto dalla lista, con $Q_1=\{1\}$, $Q_2=\{2\}$, $Q_3=\{3,7\}$ e $q(2)=3$. I vertici $4,5,6$ hanno $\mathit{sat}=1$ e lo stesso $\mathit{du}=2$: vince l'indice minimo, e il vertice di branching è $4$. I suoi colori ammissibili sono $F_{2}(4)=\{2,3\}$.
- Nodo $4$: $\mathit{col}(4)=2$, con $q(4)=3<\UB=4$: il nodo sopravvive.
- Nodo $5$: $\mathit{col}(4)=3$, con $q(5)=3<\UB=4$: il nodo sopravvive.
- Nodo $6$: $\mathit{col}(4)=4$, il colore nuovo, con $q(6)=4\ge\UB=4$: potato per bound.
**Iterazione 3**
Il nodo $4$ viene estratto dalla lista, con $Q_1=\{1\}$, $Q_2=\{2,4\}$, $Q_3=\{3,7\}$ e $q(4)=3$. I vertici $5,6$ hanno $\mathit{sat}=2$ e lo stesso $\mathit{du}=1$: vince l'indice minimo, e il vertice di branching è $5$. I suoi colori ammissibili sono $F_{4}(5)=\{1\}$.
- Nodo $7$: $\mathit{col}(5)=1$, con $q(7)=3<\UB=4$: il nodo sopravvive.
- Nodo $8$: $\mathit{col}(5)=4$, il colore nuovo, con $q(8)=4\ge\UB=4$: potato per bound.
**Iterazione 4**
Il nodo $7$ viene estratto dalla lista, con $Q_1=\{1,5\}$, $Q_2=\{2,4\}$, $Q_3=\{3,7\}$ e $q(7)=3$. Il vertice $6$ è l'unico con $\mathit{sat}=3$: è il vertice di branching. I suoi colori ammissibili sono $F_{7}(6)=\emptyset$.
- Nodo $9$: $\mathit{col}(6)=4$, il colore nuovo, con $q(9)=4\ge\UB=4$: potato per bound.
**Iterazione 5**
Il nodo $5$ viene estratto dalla lista, con $Q_1=\{1\}$, $Q_2=\{2\}$, $Q_3=\{3,4,7\}$ e $q(5)=3$. I vertici $5,6$ hanno $\mathit{sat}=1$ e lo stesso $\mathit{du}=1$: vince l'indice minimo, e il vertice di branching è $5$. I suoi colori ammissibili sono $F_{5}(5)=\{1,2\}$.
- Nodo $10$: $\mathit{col}(5)=1$, con $q(10)=3<\UB=4$: il nodo sopravvive.
- Nodo $11$: $\mathit{col}(5)=2$, con $q(11)=3<\UB=4$: il nodo sopravvive.
- Nodo $12$: $\mathit{col}(5)=4$, il colore nuovo, con $q(12)=4\ge\UB=4$: potato per bound.
**Iterazione 6**
Il nodo $10$ viene estratto dalla lista, con $Q_1=\{1,5\}$, $Q_2=\{2\}$, $Q_3=\{3,4,7\}$ e $q(10)=3$. Il vertice $6$ è l'unico con $\mathit{sat}=2$: è il vertice di branching. I suoi colori ammissibili sono $F_{10}(6)=\{2\}$.
- Nodo $13$: $\mathit{col}(6)=2$, con $q(13)=3<\UB=4$: una colorazione completa con meno colori: nuova soluzione incumbent, con $\big\{\{1,5\},~\{2,6\},~\{3,4,7\}\big\}$ e $\UB=3$.
Terminazione La nuova soluzione incumbent dà $\UB=3$. I nodi della lista con $q\ge\UB$ vengono rimossi: il nodo $11$. Poiché $\UB=\LB=3$, la soluzione incumbent è ottima: STOP.

L'albero ha $13$ nodi; i nodi potati sono tratteggiati.

Figura 12

Nodo	Padre	Figlio	$q$	$\UB$	Vertice di branching	Esito
$1$	–	radice	$3$	$4$	$7$	branching
$2$	$1$	$\mathit{col}(7)=3$	$3$	$4$	$4$	branching
$3$	$1$	$\mathit{col}(7)=4$	$4$	$4$	–	potato per bound
$4$	$2$	$\mathit{col}(4)=2$	$3$	$4$	$5$	branching
$5$	$2$	$\mathit{col}(4)=3$	$3$	$4$	$5$	branching
$6$	$2$	$\mathit{col}(4)=4$	$4$	$4$	–	potato per bound
$7$	$4$	$\mathit{col}(5)=1$	$3$	$4$	$6$	branching
$8$	$4$	$\mathit{col}(5)=4$	$4$	$4$	–	potato per bound
$9$	$7$	$\mathit{col}(6)=4$	$4$	$4$	–	potato per bound
$10$	$5$	$\mathit{col}(5)=1$	$3$	$4$	$6$	branching
$11$	$5$	$\mathit{col}(5)=2$	$3$	$4$	–	non esplorato
$12$	$5$	$\mathit{col}(5)=4$	$4$	$4$	–	potato per bound
$13$	$10$	$\mathit{col}(6)=2$	$3$	$3$	–	nuova incumbent

Quindi $\chi(G)=3$, con la colorazione ottima $\big\{\{1,5\},~\{2,6\},~\{3,4,7\}\big\}$:

Figura 13

Qui $DSATUR$ non è ottima: l'algoritmo di branch-and-bound migliora la soluzione incumbent da $4$ a $3$ colori e si ferma appena $\UB$ raggiunge il bound della clique.

Esercizio 42.5: Il branching senza simmetrie (P5)

Consideriamo il ciclo $C_5$, con $V=\{1,\dots,5\}$ e gli spigoli

\[ E=\{\{1,2\},\{1,5\},\{2,3\},\{3,4\},\{4,5\}\}, \]

disegnato qui sotto. La sua clique greedy è $K=\{1,2\}$, quindi il nodo radice colora $\mathit{col}^1(1)=1$ e $\mathit{col}^1(2)=2$.

Figura 14

Domande

Disegnare l'albero dell'algoritmo di branch-and-bound DSATUR senza potatura (nessun upper bound): in ogni nodo, il vertice di branching e un figlio per ogni colore ammissibile e per il colore nuovo. Contarne i nodi e le foglie.
Elencare le partizioni di $V$ date dalle foglie, per numero di colori, e stabilire se sono tutte le partizioni di $V$ in insiemi stabili.
Contare gli assegnamenti dei cinque colori $1,\dots,5$ ai vertici senza spigoli con colori uguali, e spiegare la differenza con il numero di foglie.
Con l'upper bound $\UB=3$ di $DSATUR$ e la regola di potatura, contare i nodi dell'albero.

Soluzione

Usiamo le regole (D1)–(D5) del riquadro all'inizio del capitolo.

Ogni nodo interno mostra il suo vertice di branching, ogni arco il colore assegnato a quel vertice (in blu), ogni foglia le sue classi di colore, una per riga:

L'albero ha $19$ nodi e $11$ foglie.

Le foglie, per numero di colori:

colori	foglie	partizioni
$3$	$5$	$\{\{1\},\{2,4\},\{3,5\}\}$
		$\{\{1,3\},\{2,4\},\{5\}\}$
		$\{\{1,3\},\{2,5\},\{4\}\}$
		$\{\{1,4\},\{2\},\{3,5\}\}$
		$\{\{1,4\},\{2,5\},\{3\}\}$
$4$	$5$	$\{\{1\},\{2\},\{3,5\},\{4\}\}$
		$\{\{1\},\{2,4\},\{3\},\{5\}\}$
		$\{\{1\},\{2,5\},\{3\},\{4\}\}$
		$\{\{1,3\},\{2\},\{4\},\{5\}\}$
		$\{\{1,4\},\{2\},\{3\},\{5\}\}$
$5$	$1$	$\{\{1\},\{2\},\{3\},\{4\},\{5\}\}$

Le $11$ foglie danno $11$ partizioni diverse, e l'enumerazione di tutte le partizioni di $V$ in insiemi stabili dà le stesse $11$: ogni soluzione ammissibile compare esattamente una volta, come afferma la proposizione sul branching senza simmetrie.

Per enumerazione, $1020$ assegnamenti. Una partizione con $q$ classi si può etichettare con $5\cdot4\cdots(5-q+1)$ scelte ordinate di colori, quindi

\[ 5\cdot60+5\cdot120+1\cdot120=1020. \]

Le colorazioni etichettate contengono ogni partizione molte volte, con i colori rinominati; l'albero contiene ciascuna una volta sola.
Con la potatura restano $6$ nodi invece di $19$: ogni nodo con $q=3$ è potato, e la ricerca dimostra $\chi(C_5)=3$ lungo un solo cammino, come nel primo esercizio di questo capitolo.

Senza potatura, l'albero di $C_5$ ha $11$ foglie, una per ogni partizione in insiemi stabili, contro $1020$ colorazioni etichettate; con $\UB=3$ restano solo $6$ nodi.

passo	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)
\(v\)	\(2\)	\(3\)	\(1\)	\(4\)	\(5\)	\(6\)
\(\mathit{sat}(v)\)	\(0\)	\(1\)	\(2\)	\(1\)	\(1\)	\(2\)
\(\mathit{du}(v)\)	\(3\)	\(2\)	\(0\)	\(2\)	\(1\)	\(0\)
\(\mathit{col}(v)\)	\(1\)	\(2\)	\(3\)	\(2\)	\(1\)	\(3\)

passo	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(v\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(\mathit{sat}(v)\)	\(0\)	\(1\)	\(1\)	\(1\)	\(2\)
\(\mathit{du}(v)\)	\(2\)	\(1\)	\(1\)	\(1\)	\(0\)
\(\mathit{col}(v)\)	\(1\)	\(2\)	\(1\)	\(2\)	\(3\)

passo	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)
\(v\)	\(6\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(\mathit{sat}(v)\)	\(0\)	\(1\)	\(2\)	\(2\)	\(2\)	\(3\)
\(\mathit{du}(v)\)	\(5\)	\(2\)	\(1\)	\(1\)	\(1\)	\(0\)
\(\mathit{col}(v)\)	\(1\)	\(2\)	\(3\)	\(2\)	\(3\)	\(4\)

Nodo	Padre	Figlio	\(q\)	\(\UB\)	Vertice di branching	Esito
\(1\)	–	radice	\(3\)	\(4\)	\(3\)	branching
\(2\)	\(1\)	\(\mathit{col}(3)=2\)	\(3\)	\(4\)	\(4\)	branching
\(3\)	\(1\)	\(\mathit{col}(3)=4\)	\(4\)	\(4\)	–	potato per bound
\(4\)	\(2\)	\(\mathit{col}(4)=3\)	\(3\)	\(4\)	\(5\)	branching
\(5\)	\(2\)	\(\mathit{col}(4)=4\)	\(4\)	\(4\)	–	potato per bound
\(6\)	\(4\)	\(\mathit{col}(5)=4\)	\(4\)	\(4\)	–	potato per bound

passo	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)
\(v\)	\(1\)	\(3\)	\(5\)	\(6\)	\(4\)	\(2\)	\(7\)
\(\mathit{sat}(v)\)	\(0\)	\(1\)	\(2\)	\(2\)	\(2\)	\(2\)	\(3\)
\(\mathit{du}(v)\)	\(4\)	\(3\)	\(2\)	\(2\)	\(2\)	\(1\)	\(0\)
\(\mathit{col}(v)\)	\(1\)	\(2\)	\(3\)	\(3\)	\(2\)	\(1\)	\(4\)

colori	foglie	partizioni
\(3\)	\(5\)	\(\{\{1\},\{2,4\},\{3,5\}\}\)
		\(\{\{1,3\},\{2,4\},\{5\}\}\)
		\(\{\{1,3\},\{2,5\},\{4\}\}\)
		\(\{\{1,4\},\{2\},\{3,5\}\}\)
		\(\{\{1,4\},\{2,5\},\{3\}\}\)
\(4\)	\(5\)	\(\{\{1\},\{2\},\{3,5\},\{4\}\}\)
		\(\{\{1\},\{2,4\},\{3\},\{5\}\}\)
		\(\{\{1\},\{2,5\},\{3\},\{4\}\}\)
		\(\{\{1,3\},\{2\},\{4\},\{5\}\}\)
		\(\{\{1,4\},\{2\},\{3\},\{5\}\}\)
\(5\)	\(1\)	\(\{\{1\},\{2\},\{3\},\{4\},\{5\}\}\)