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'.