Vai al contenuto

5.5 Varianti pesate

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 5 · Capitolo 5: Problemi di clique · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di clique

  • Sia \(\vet{w} \in \Z_{\ge 1}^n\) un vettore dei pesi dei vertici, con un peso \(w_v\) per ogni vertice \(v \in V\), e sia \(\vet{r} \in \Z_{\ge 1}^m\) un vettore dei pesi dei lati, con un peso \(r_{uv}\) per ogni lato \(\{u,v\} \in E\). Per una clique \(K\) definiamo

    \[ w(K) = \sum_{v \in K} w_v \qquad\text{e}\qquad r(K) = \sum_{\{u,v\} \in E[K]} r_{uv}, \]

    dove \(E[K]\) è l'insieme dei lati con entrambi gli estremi in \(K\).

Definizione 5.10: problemi della clique massima pesata

  1. Dati un grafo \(G\) e un vettore dei pesi dei vertici \(\vet{w}\), il problema della clique massima pesata sui vertici (VWMCP) chiede di trovare una clique \(K\) di \(G\) con peso totale dei vertici \(w(K)\) massimo.

  2. Dati un grafo \(G\) e un vettore dei pesi dei lati \(\vet{r}\), il problema della clique massima pesata sui lati (EWMCP) chiede di trovare una clique \(K\) di \(G\) con peso totale dei lati \(r(K)\) massimo.

  • Con tutti i pesi \(w_v=1\) il primo problema è il MCP. Il problema pesato sui lati premia le clique con molti lati pesanti, e con \(r_{uv}=1\) è di nuovo il MCP, poiché \(r(K)=\binom{|K|}{2}\) cresce con \(|K|\).

Esempio 5.3: problema della clique massima pesata sui vertici

Aggiungiamo al grafo dell'Esempio 5.2 i pesi dei vertici in blu. La clique massima pesata sui vertici è \(\{2,3,5,8\}\), con peso \(8+9+6+9=32\): è unica, e non è la clique massima in rosso dell'Esempio 5.2, il cui peso è \(5+9+5+5=24\).

Figura 3

Una clique prende al più un vertice da ciascuna coppia \(\{1,5\},\{2,6\},\{3,7\},\{4,8\}\); prendere il più pesante di ciascuna coppia dà \(6+8+9+9=32\), e questi quattro vertici formano una clique.

Esempio 5.4: problema della clique massima pesata sui lati

Aggiungiamo al grafo dell'Esempio 5.2 i pesi dei lati in rosso. La clique massima pesata sui lati è \(\{2,5,7,8\}\), in arancione: i suoi sei lati pesano \(6+4+9+7+3+8=37\), e l'enumerazione delle \(16\) clique massime mostra che è l'unica soluzione ottima.

Figura 4

5.6 Osservazioni

  • In una colorazione, ogni classe di colore è un insieme stabile: il MSSP è il problema della classe di colore più grande, e il numero di clique è il bound duale del Capitolo 4 «Problemi di colorazione».

  • Applicazioni delle clique e degli insiemi stabili:

    • gruppi di membri a due a due connessi nelle reti sociali;

    • gruppi di attività o di esami a due a due compatibili, nello scheduling e nella pianificazione degli orari;

    • sottostrutture comuni a due molecole, in chimica e in biologia;

    • codici a correzione d'errore, come grandi insiemi di parole a due a due lontane.

5.7 Errori tipici

Attenzione

  • Confondere una clique massimale con una clique massima. Una clique è massimale quando non le si può aggiungere alcun vertice; è massima quando nessuna clique è più grande. Nell'Esempio 5.1, \(\{4,5\}\) è massimale ma non massima.

  • Costruire il grafo complementare con i lati di \(G\). I lati di \(\overline{G}\) sono esattamente le coppie che non sono lati di \(G\): sono \(\binom{n}{2}-m\).

  • Usare un lower bound come upper bound. Una clique trovata a mano dà \(\LB \le \omega(G)\); i bound sui gradi e una colorazione danno \(\UB \ge \omega(G)\). In questo capitolo il problema è di massimo.

  • Credere che il bound di colorazione sia stretto. Sul ciclo con \(5\) vertici \(\omega(G)=2\) e \(\chi(G)=3\).

5.8 In sintesi

In sintesi

  • Il MCP cerca il più grande insieme di vertici a due a due adiacenti; il suo valore ottimo è il numero di clique \(\omega(G)\).

  • Una clique di \(G\) è un insieme stabile di \(\overline{G}\): il MCP su \(G\) è il MSSP su \(\overline{G}\), e \(\omega(G)=\alpha(\overline{G})\).

  • Una clique trovata a mano è un bound primale; il bound sul grado, il bound sui lati, il bound sul conteggio dei gradi e il numero di colori di una colorazione sono bound duali.

  • Il MCP è NP-difficile e difficile da approssimare; le sue varianti pesate pesano i vertici o i lati.

Quadro riassuntivo delle istanze di riferimento.

istanza (max) lower bound upper bound da
Esempio 5.1 (ciclo con corda) \(3\) (a mano) \(3\) (conteggio dei gradi, colorazione) questo capitolo
Esempio 5.2 (grafo denso) \(4\) (a mano) \(4\) (colorazione) questo capitolo

Esercizi su questo capitolo: Problemi di clique

Approfondimento: che cosa fa il corso su questo problema