Vai al contenuto

Problemi di colorazione

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 4 · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di colorazione · App: Colorazione: greedy e DSATUR

Prerequisiti

Obiettivi

Al termine di questo capitolo saremo in grado di:

  • usare le nozioni di base sui grafi: intorno, grado, grafo indotto, grafo complementare, clique e insieme stabile;

  • enunciare la definizione del problema della colorazione dei vertici e le ipotesi sul grafo;

  • contare le soluzioni candidate di una piccola istanza e riconoscere che sono partizioni;

  • trovare a mano una colorazione e calcolare il bound di clique e il bound degli insiemi stabili;

  • spiegare perché il bound di clique non è sempre stretto.

4.1 Panoramica della famiglia

  • I problemi di colorazione hanno gli stessi dati: un grafo semplice non orientato \(G = (V,E)\), i cui lati sono le coppie di vertici in conflitto.

  • Una soluzione assegna un colore a ogni vertice, in modo che i due estremi di ogni lato ricevano colori diversi: i vertici con lo stesso colore formano un insieme stabile di \(G\).

  • L'obiettivo è minimizzare il numero di colori usati.

Un problema di colorazione partiziona i vertici di un grafo nel minor numero di insiemi stabili. Le nozioni sui grafi della sottosezione seguente sono la notazione comune della famiglia.

  • La tabella elenca i membri della famiglia, con la sezione che definisce ciascuno di essi.
Problema Sigla Soluzione Sezione
problema della colorazione dei vertici VCP una partizione di \(V\) in insiemi stabili 4.2

4.1.1 Un breve richiamo sui grafi

Definizione 4.1: grafo, intorno, grafo indotto e grafo complementare

  • Un grafo \(G = (V,E)\) è dato da un insieme finito \(V\) di vertici e da un insieme \(E\) di lati, ciascuno dei quali è un sottoinsieme di \(2\) elementi di \(V\). Scriviamo \(n = |V|\) e \(m = |E|\); i vertici sono etichettati \(1,2,\dots,n\). Tutti i grafi di questo capitolo sono semplici e non orientati.

  • Due vertici distinti \(u\) e \(v\) sono adiacenti se \(\{u,v\} \in E\). L'intorno di un vertice \(v\) è l'insieme \(N(v) = \{\, u \in V : \{u,v\} \in E \,\}\), e il suo grado è \(\deg(v) = |N(v)|\).

  • Per un sottoinsieme \(U \subseteq V\) il grafo indotto \(G[U] = (U, E[U])\) ha i vertici di \(U\) e i lati di \(E\) con entrambi gli estremi in \(U\).

  • Il grafo complementare \(\overline{G} = (V, \overline{E})\) ha gli stessi vertici di \(G\), e due vertici distinti sono adiacenti in \(\overline{G}\) se e solo se non sono adiacenti in \(G\).

Definizione 4.2: clique e insieme stabile

Sia \(G = (V,E)\) un grafo.

  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\).

  2. Un insieme stabile (detto anche insieme indipendente) è un sottoinsieme \(Q \subseteq V\) di vertici a due a due non adiacenti: \(\{u,v\} \notin E\) per ogni \(u,v \in Q\) con \(u \neq v\).

Il numero di clique \(\omega(G)\) è il massimo numero di vertici di una clique, e il numero di stabilità \(\alpha(G)\) è il massimo numero di vertici di un insieme stabile.

  • Un insieme stabile di \(G\) è una clique del grafo complementare \(\overline{G}\), e viceversa. Un vertice da solo e l'insieme vuoto sono sia una clique sia un insieme stabile.

Una clique è un gruppo di vertici a due a due in conflitto; un insieme stabile è un gruppo di vertici senza conflitti. In una colorazione, i vertici di una clique richiedono colori diversi, e i vertici di un insieme stabile possono condividerne uno.

  • Panoramica

    Panoramica della famiglia · Un breve richiamo sui grafi

    Apri

  • 4.2 Il problema della colorazione dei vertici

    Due bound semplici · Contare le soluzioni, una prima soluzione e i bound · Osservazioni · Errori tipici · In sintesi

    Apri

Avanti: 4.2 Il problema della colorazione dei vertici

Esercizi su questo capitolo: Problemi di colorazione

Approfondimento: che cosa fa il corso su questo problema

Nel laboratorio interattivo: Colorazione: greedy e DSATUR.