Cobertura de vértices (teoria dos grafos)
De Wikipedia, a enciclopédia encyclopedia
Na matemática, na disciplina de teoria dos grafos, uma cobertura de vertices de um grafo é um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do conjunto. Ou seja, É um conjunto de vértices que contém pelo menos uma das pontas de cada aresta. Em outras palavras, uma cobertura de vértices é um conjunto V de vértices dotado da seguinte propriedade: toda aresta do grafo tem pelo menos uma ponta em V.
O problema de encontrar uma cobertura de vértices mínima é um clássico problema de otimização em ciência da computação e é um exemplo típico de um problema de otimização NP-difícil que tem um algoritmo de aproximação. Esta versão de problema de decisão, o problema da cobertura de vértices, foi um dos 21 problemas NP-completos de Karp e, portanto, um problema NP-completo clássico da teoria da complexidade computacional. Além disso, o problema de cobertura de vértices é tratável em parâmetros fixos e um problema central na teoria da complexidade parametrizada.
O problema da cobertura de vértices mínima pode ser formulado como um semi-integral programa linear cujo programa linear dual é o problema do acoplamento máximo.