DAA - Copertura Vertex

Una copertura del vertice di un grafo non orientato G = (V, E) è un sottoinsieme di vertici V^' ⊆ V tale che se bordo (u, v) è un vantaggio di G, allora neanche u in V o v in V^' o entrambi.

Trova una copertura del vertice della dimensione massima in un dato grafo non orientato. Questo vertexcover ottimale è la versione di ottimizzazione di un problema NP-completo. Tuttavia, non è troppo difficile trovare una copertura del vertice che sia quasi ottimale.

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

Esempio

L'insieme dei bordi del grafico dato è -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Ora, iniziamo selezionando un arco arbitrario (1,6). Eliminiamo tutti i bordi, che sono incidenti al vertice 1 o 6 e aggiungiamo il bordo (1,6) alla copertura.

Nel passaggio successivo, abbiamo scelto un altro arco (2,3) a caso

Ora selezioniamo un altro bordo (4,7).

Selezioniamo un altro bordo (8,5).

Quindi, la copertura del vertice di questo grafico è {1,2,4,5}.

Analisi

È facile vedere che il tempo di esecuzione di questo algoritmo è O(V + E), utilizzando l'elenco di adiacenza per rappresentare E^'.