Cobertura de vértices

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

Es de especial interés encontrar pequeños conjuntos con esta propiedad. El problema de encontrar el menor nodo covering es llamado problema problema del nodo cover y es NP-completo

Coverings con vértices y arcos están muy relacionados con conjuntos independientes y matchings.

Definición

Un nodo covering 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\,$ . El mínimo nodo covering es el más pequeño nodo cover. Llamamos $V\,$ covers a los vértices del grafo. El número de node cover $\omega _{V}(G)\,$ para un grafo $G\,$ es el tamaño del mínimo nodo covering.

Un arco covering para un grafo $G\,$ es un conjunto de arcos $E\,$ en los que cada nodo de $G\,$ son adyacentes al menos a un arco de $E\,$ . El mínimo arco covering es el menor arco covering. Llamamos $E\,$ covers a los vertices del grafo. El número de arco covering $\omega _{E}(G)\,$ de un grafo $G\,$ es el tamaño del mínimo arco covering.

Cuando se habla de covering se refiere normalmente al nodo covering.

Ejemplos

para cualquier grafo $G\,$ el conjunto de todos sus vértices (arcos) es trivialmente un nodo covering (covering de nodos)
Un grafo completo bipartido $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 \,$

La figura muestra un grafo $G=(V,E)\,$ no orientado y conexo. $V\subseteq \;V^{\prime }$ es un nodo cover si $\forall e\in \ E$ al menos uno de los puntos finales de $e\,$ finaliza en $V^{\prime }\,$