Vai al contenuto

Problemi di clique

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

Prerequisiti

Obiettivi

Al termine di questo capitolo saremo in grado di:

  • enunciare il problema della clique massima e il problema dell'insieme stabile massimo, e passare dall'uno all'altro attraverso il grafo complementare;

  • descrivere un'istanza e una soluzione ammissibile, e contare le soluzioni candidate di un piccolo grafo;

  • trovare a mano una clique e calcolare quattro semplici upper bound sul numero di clique;

  • enunciare le varianti pesate del problema e la sua complessità.

5.1 Panoramica della famiglia

  • I problemi di clique hanno gli stessi dati: un grafo semplice non orientato \(G = (V,E)\), con \(V = \{1,2,\dots,n\}\) e \(m\) lati, eventualmente con pesi sui vertici o sui lati.

  • Una soluzione è una clique di \(G\), ossia un sottoinsieme di vertici a due a due adiacenti.

  • L'obiettivo è massimizzare la cardinalità della clique, o il suo peso totale.

Definizione 5.1: clique e numero di clique

Sia \(G=(V,E)\) un grafo semplice non orientato con \(n\) vertici e \(m\) lati.

  1. Una clique è un sottoinsieme \(K \subseteq V\) di vertici a due a due adiacenti: \(\{u,v\} \in E\) per ogni \(u,v \in K\) con \(u \neq v\). Equivalentemente, \(K\) induce un grafo completo.

  2. Il numero di clique \(\omega(G)\) è il massimo numero di vertici di una clique di \(G\).

Un problema di clique seleziona una clique di cardinalità massima o di peso massimo. Sul grafo complementare \(\overline{G}\) gli stessi problemi selezionano insiemi stabili.

  • La tabella elenca i membri della famiglia, con la sezione che definisce ciascuno di essi.
Problema Sigla Obiettivo Sezione
clique massima MCP massimo numero di vertici di una clique 5.2
insieme stabile massimo MSSP massimo numero di vertici di un insieme stabile 5.2
clique massima pesata sui vertici VWMCP massimo peso totale dei vertici 5.5
clique massima pesata sui lati EWMCP massimo peso totale dei lati 5.5

  • Panoramica

    Panoramica della famiglia

    Apri

  • 5.2 Il problema della clique massima

    Upper bound semplici

    Apri

  • 5.5 Varianti pesate

    Errori tipici · In sintesi

    Apri

Avanti: 5.2 Il problema della clique massima

Esercizi su questo capitolo: Problemi di clique

Approfondimento: che cosa fa il corso su questo problema