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 arcos (o vértices) del grafo.

Es de especial interes 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 estan 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 node cover. Llamamos $V\,$ covers a los arcos del grafo. El número de node cover $\omega _{V}(G)\,$ para un grafo $G\,$ es el tamaño del mínimo node 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 node covering.

Ejemplos

ejemplo nodo cover

• para cualquier grafo $G\,$ el conjunto de sus vértices (arcos) es trivialmente un node 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 y su complementario G'. En esta figura G' tiene un nodo cover de $\{4,5\}\,$, ya que cada arco de G' incide o en el nodo 4 o en el nodo 5. Por lo tanto, G tiene un clique (liga) de tamaño 5-2=3 consistente en los nodos $\{1,2,3\}\,$.

Propiedades

• Para cualquier grafo $G:=(V,E)\,$ : $\omega _{V}(G)\,$ + máximo conjunto de vértices independientes = ${\Big |}V\ {\Big |}$ (Tibor Gallai 1959)

Referencias

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

[[Categoría:Investigación Operativa]