Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 18.Il Problema del Vertex Cover Minimo di un Grafo


Il Problema del Vertex Cover Minimo, 1

Dato un grafo non orientato G=(V,E), un sottoinsieme V’ non proprio di V è detto vertex cover per G se per ogni arco di G almeno uno dei vertici ad esso incidenti appartiene a V’.
Formalmente, tale proprietà di V’ è espressa come segue.
Definizione. V’ è un vertex cover per il grafo G=(V,E) se per ogni arco [i,j] in E, almeno una delle seguenti condizioni è verificata:

  • i appartiene a V’;
  • j appartiene a V’.

Dato un grafo non orientato G=(V,E), il Problema del Vertex Cover Minimo (VC) consiste nel trovare un vertex cover per G di cardinalità minima.

VC è un problema “difficile” dal punto di vista computazionale.
Studieremo in quanto segue la sua descrizione logico-matematica ed un algoritmo 2-approssimato di tipo random.

Il Problema del Vertex Cover Minimo, 2

Introducendo le seguenti \vert V\vert=n variabili di decisione

\[ \forall\ j=1,2,\ldots,n,\\ x_j=\left\{ \begin{array}{lll}1& \mbox{{\rm se $j\in V'$}}\\ 0&\mbox{{\rm altrimenti,}}\end{array} \right.\]

si ottiene la seguente formulazione matematica per il Problema del Vertex Cover Minimo di G:
\[  \begin{array}{llll} \mbox{(VC)} & \mbox{{\rm min}} & \displaystyle{\sum_{j=1}^n x_j}\\ & \mbox{{\rm s.a}} \\ &        & x_i+x_j \geq 1, & \forall\ [i,j]\in E \\ \\ &        & x_j\in\{0,1\},  & j=1,2,\ldots,n. \end{array} \]

Il Problema del Vertex Cover Minimo, 3

Come già sottolineato, il Problema del Vertex Cover Minimo di un grafo G è un problema “difficile”, per cui a tutt’oggi un qualunque algoritmo esatto per esso ha complessità computazionale superpolinomiale.
Tuttavia , è possibile individuare una soluzione approssimata in tempo polinomiale.

In quanto segue verrà descritto un algoritmo polinomiale di approssimazione che, preso in input un grafo non orientato G=(V,E), trova con complessità O(\vert E\vert) un vertex cover V’ per G di taglia al più due volte la taglia di un vertex cover ottimo V*, ossia
\[ \vert V'\vert\leq 2\ \vert V^*\vert. \]

Il Problema del Vertex Cover Minimo, 4

2-approx-vc: un algoritmo polinomiale di approssimazione per il Problema del Vertex Cover Minimo di un grafo.

\fbox{\begin{minipage}[h]{11cm} \footnotesize{ \begin{tt} {\bf algoritmo} {$2$-approx-vc} ($V$,$E$)\\ $1$\hspace*{0.5truecm} $V':=\emptyset$; $E':=E$;\\ $2$\hspace*{0.5truecm} {\bf while} ($E'\not=\emptyset$) {\bf do} \\ $3$\hspace*{1truecm} $[i,j]=$select($E'$);\hspace*{0.2truecm} \mbox{/* seleziona da $E'$ un arco a caso */}\\ $4$\hspace*{1truecm} $V':=V'\cup\{i,j\}$; \\ $5$\hspace*{1truecm} $E':=E'\setminus\{[u,v]\ \vert\ v=i\ \mbox{o}\ u=j\}$; \\ $6$\hspace*{0.5truecm} {\bf endwhile} \\ $7$\hspace*{0.5truecm} {\bf return} ($V'$); \\ {\bf end} {$2$-approx-vc} \hspace*{0.2truecm} \mbox{/*$O(\vert E\vert)=O(m)$ */} \end{tt} } \end{minipage}}

Il Problema del Vertex Cover Minimo, 5

Teorema. L’insieme V’ restituito in output da 2-approx-vc è un vertex cover per G tale che
\[ \vert V'\vert\leq 2\ \vert V^*\vert.\]
Dimostrazione. V’ restituito in output è un vertex cover per G per costruzione.
Indichiamo con A l’insieme degli archi selezionati a caso da E’ (linea 3).
Per ogni arco [i,j] in A, i e j sono aggiunti a V’ (linea 4), per cui si ha che |V’|=2|A|.
Inoltre, vengono rimossi da E’ tutti gli archi incidenti in almeno uno fra i vertici i e j (linea 5), per cui due archi in A non possono essere adiacenti. Conseguenza di quest’ultima osservazione è che
\[ \vert A\vert\leq\vert V^*\vert, \]
da cui la tesi.

Il Problema del Vertex Cover Minimo, 6

Esempio 1. Si applichi 2-approx-vc per trovare un vertex cover approssimato per il grafo riportato in Figura (a).
Inizialmente, E’:=E.

I it.: supponiamo di scegliere da E’ l’arco [1,2].
V’={1,2}, mentre E’={[4,3]}.

II it.
: l’unico arco che può essere selezionato da E’ è [4,3].
V’= {1,2,3,4}=V, mentre E’ diventa un ins. vuoto –> STOP.

Nota: |V’|=2 |V*|.

(a) un grafo non orientato avente 4 nodi e 5 archi; 
(b) un grafo non orientato avente 4 nodi e 5 archi. Disegnata da Paola Festa

(a) un grafo non orientato avente 4 nodi e 5 archi; (b) un grafo non orientato avente 4 nodi e 5 archi. Disegnata da Paola Festa


Il Problema del Vertex Cover Minimo, 7

Se applicassimo 2-approx-vc per trovare un vertex cover approssimato per il grafo riportato in Figura (b) e alla I it. l’algoritmo scegliesse ancora una volta l’arco [1,2], allora il vertex cover V’={1,2} restituito in output sarebbe un vertex cover ottimo.

(a) un grafo non orientato avente 4 nodi e 5 archi; 
(b) un grafo non orientato avente 4 nodi e 5 archi. Disegnata da Paola Festa

(a) un grafo non orientato avente 4 nodi e 5 archi; (b) un grafo non orientato avente 4 nodi e 5 archi. Disegnata da Paola Festa


Il Problema del Vertex Cover Minimo, 8

Esempio. Si applichi 2-approx-vc per trovare un vertex cover approssimato per il grafo riportato in Figura.
Inizialmente, E’:=E.

I it.: supponiamo di scegliere da E’ l’arco [1,2].
V’={1,2}, mentre E’ diventa un insieme vuoto –> STOP.

Un grafo non orientato avente 7 nodi e 6 archi. Disegnata da Paola Festa

Un grafo non orientato avente 7 nodi e 6 archi. Disegnata da Paola Festa


I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion