Cobertura de vértices

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Ejemplos de coberturas de vértices (conformadas por los vértices en rojo).
Ejemplos de coberturas de vértices mínimas.

En matemáticas, en el campo de la teoría de grafos, una cobertura de vértices (en inglés, vertex covering) o simplemente cobertura de un grafo, es un conjunto de vértices cuyos elementos son adyacentes a todos los vértices o nodos del grafo.

Es de especial interés encontrar pequeños conjuntos que cumplen esta propiedad. El problema de encontrar la menor cobertura de vértices se llama Problema de la cobertura de vértices y es NP-completo.

La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes y apareamientos o matchings.

Definición[editar]

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. La cobertura de vértices mínima es la más pequeña de las coberturas de vértices. El número de cobertura de vértices \omega_V(G)\, para un grafo G es el tamaño de la cobertura de vértices mínima.

Ejemplos[editar]

  • Para cualquier grafo, el conjunto de todos sus vértices es trivialmente una cobertura de vértices.
  • Un grafo bipartito completo G_{m,n}\, tiene \omega_V(G_{m,n})=\min\lbrace m,n \rbrace\, y \omega_E(G_{m,n})=\max \lbrace m,n \rbrace\,.

Propiedades[editar]

Véase también[editar]

Referencias[editar]

  • Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.