- 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 del nodo cover y es NP-completo.
Coverings con vértices y arcos están muy relacionados con conjuntos independientes y matchings.
Contenido
Definición
Un nodo covering para un grafo
es un conjunto de vértices
en los que cada arco de
incide al menos en un nodo de
. El mínimo nodo covering es el más pequeño nodo cover. Llamamos
covers a los vértices del grafo. El número de node cover
para un grafo
es el tamaño del mínimo nodo covering.
Un arco covering para un grafo
es un conjunto de arcos
en los que cada nodo de
es adyacente al menos a un arco de
. El mínimo arco covering es el menor arco covering. Llamamos
covers a los vértices del grafo. El número de arco covering
de un grafo
es el tamaño del mínimo arco covering.
Cuando se habla de covering se hace referencia normalmente al nodo covering.
Ejemplos
grafo G- para cualquier grafo
el conjunto de todos sus vértices (arcos) es trivialmente un nodo covering (covering de nodos)
- Un grafo completo bipartido
tiene
y
La figura muestra un grafo
no orientado y conexo.
es un nodo cover si
al menos uno de los puntos finales de
finaliza en
- ejemplos:
tamaño del nodo cover
Propiedades
- Para cualquier grafo
:
+ máximo conjunto de vértices independientes =
(Tibor Gallai 1959)
Véase también
Referencias
- Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
- para cualquier grafo
Wikimedia foundation. 2010.