Cobertura de vértices
En la disciplina matemática de la teoría de grafos, una cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada arista del grafo es incidente a al menos un vértice del conjunto.
En teoría de la complejidad computacional se ha demostrado que este es un problema NP-completo.
La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes y apareamientos o matchings.
Una cobertura de vértices para un grafo G es un conjunto de vértices V en los que cada arco de G incide al menos en un nodo de V.
para un grafo G es el tamaño de la cobertura de vértices mínima.
