DAA - Capa de Vértice

Uma cobertura de vértice de um gráfico não direcionado G = (V, E) é um subconjunto de vértices V' ⊆ V tal que se borda (u, v) é uma borda de G, qualquer então u dentro V ou v dentro V' ou ambos.

Encontre uma cobertura de vértice de tamanho máximo em um dado gráfico não direcionado. Esta cobertura de vértice ideal é a versão de otimização de um problema NP-completo. No entanto, não é muito difícil encontrar uma cobertura de vértices próxima da ideal.

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

Exemplo

O conjunto de arestas do gráfico fornecido é -

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

Agora, começamos selecionando uma aresta arbitrária (1,6). Eliminamos todas as arestas que são incidentes ao vértice 1 ou 6 e adicionamos a aresta (1,6) para cobrir.

Na próxima etapa, escolhemos outra aresta (2,3) aleatoriamente

Agora selecionamos outra aresta (4,7).

Selecionamos outra aresta (8,5).

Portanto, a cobertura do vértice deste gráfico é {1,2,4,5}.

Análise

É fácil ver que o tempo de execução deste algoritmo é O(V + E), usando lista de adjacência para representar E'.