Diferencia entre revisiones de «Cobertura de vértices»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 16:27 4 jul 2012

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 (en inglés, covering) de un grafo es un conjunto de vértices (o aristas) cuyos elementos son cerrados (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 el menor vértice de cobertura 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

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.

Una cobertura de aristas para un grafo G es un conjunto de aristas E en las que cada vértice de G es adyacente al menos a una arista de E. La cobertura de aristas mínima es la cobertura de aristas más pequeña. El número de cobertura de aristas $\omega _{E}(G)\,$ de un grafo G es el tamaño de la cobertura de aristas mínima.

Cuando se habla de cobertura o covering se hace referencia normalmente a la cobertura de vértices.

Ejemplos

Para cualquier grafo, el conjunto de todos sus vértices (o aristas) es trivialmente una cobertura de vértices (o aristas).
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

Para cualquier grafo $G=(V,E)\,$ : $\omega _{V}(G)\,$ + máximo conjunto de vértices independientes = ${\Big |}V\ {\Big |}$ (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.

@@ Línea 1: / Línea 1: @@
+[[Archivo:Vertex-cover.svg|thumb|Ejemplos de coberturas de vértices (conformadas por los vértices en rojo).]]
-En matemáticas, en el campo de la [[teoría de grafos]], un '''covering''' de un [[grafo]] es un conjunto de [[vértice (teoría de grafos)|vértices]] (o arcos) cuyos elementos son ''cerrados'' ([[grafo|adyacentes]]) a todos los vértices (o nodos) del grafo.
+[[Archivo:Minimum-vertex-cover.svg|thumb|Ejemplos de coberturas de vértices mínimas.]]
+En matemáticas, en el campo de la [[teoría de grafos]], una '''cobertura''' (en inglés, '''covering''') de un [[grafo]] es un conjunto de [[vértice (teoría de grafos)|vértices]] (o [[arista (teoría de grafos)|aristas]]) cuyos elementos son ''cerrados'' ([[grafo|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]].
+Es de especial interés encontrar pequeños conjuntos que cumplen esta propiedad. El problema de encontrar el menor '''vértice de cobertura''' se llama [[Problema de la cobertura de vértices]] y es [[NP-completo]].
-Coverings con vértices y arcos están muy relacionados con [[conjunto independiente|conjuntos independientes]] y [[matching]]s.
+La cobertura de vértices y aristas está muy relacionada con los [[conjunto independiente|conjuntos independientes]] y [[Apareamiento (teoría de grafos)|apareamientos]] o ''matchings''.
 == Definición ==
-Un '''nodo covering''' para un grafo <math>G\,</math> es un conjunto de vértices <math>V\,</math> en los que cada arco de <math>G\,</math> incide al menos en un nodo de <math>V\,</math>. El '''mínimo nodo covering''' es el más pequeño nodo cover. Llamamos <math>V\,</math> ''covers'' a los vértices del grafo.
+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 node cover''' <math>\omega_V(G)\,</math> para un grafo <math>G\,</math> es el tamaño del mínimo nodo covering.
+El '''número de cobertura de vértices''' <math>\omega_V(G)\,</math> para un grafo ''G'' es el tamaño de la cobertura de vértices mínima.
-Un '''arco covering''' para un grafo <math>G\,</math> es un conjunto de arcos <math>E\,</math> en los que cada nodo de <math>G\,</math> es adyacente al menos a un arco de <math>E\,</math>. El '''mínimo arco covering''' es el menor arco covering. Llamamos <math>E\,</math> covers a los vértices del grafo. El '''número de arco covering''' <math>\omega_E(G)\,</math> de un grafo <math>G\,</math> es el tamaño del mínimo arco covering.
+Una '''cobertura de aristas''' para un grafo ''G'' es un conjunto de aristas ''E'' en las que cada vértice de ''G'' es adyacente al menos a una arista de ''E''. La '''cobertura de aristas mínima''' es la cobertura de aristas más pequeña. El '''número de cobertura de aristas''' <math>\omega_E(G)\,</math> de un grafo ''G'' es el tamaño de la cobertura de aristas mínima.
-Cuando se habla de '''covering''' se hace referencia normalmente al ''nodo covering''.
+Cuando se habla de '''cobertura''' o '''covering''' se hace referencia normalmente a la cobertura de vértices.
 == Ejemplos ==
+* Para cualquier grafo, el conjunto de todos sus vértices (o aristas) es trivialmente una cobertura de vértices (o aristas).
-[[Image:NodoCover2.PNG|frame|right|grafo G]]
+* Un [[grafo bipartito completo]] <math>G_{m,n}\,</math> tiene <math>\omega_V(G_{m,n})=\min\lbrace m,n \rbrace\,</math> y <math>\omega_E(G_{m,n})=\max \lbrace m,n \rbrace\,</math>.
-* para cualquier grafo <math>G\,</math> el conjunto de todos sus vértices (arcos) es trivialmente un nodo covering (covering de nodos)
-* Un [[grafo completo bipartido]] <math>G_{m,n}\,</math> tiene <math>\omega_V(G_{m,n})=\min\lbrace m,n \rbrace\,</math> y <math>\omega_E(G_{m,n})=\max \lbrace m,n \rbrace\,</math>
-La figura muestra un [[grafo]] <math>G = (V,E) \,</math> no orientado y conexo.
-<math>V \subseteq \; V^\prime </math> es un nodo cover si <math> \forall e \in\ E </math> al menos uno de los puntos finales de <math>e\,</math> finaliza en <math>V^\prime\,</math>
-:ejemplos:
-::<math>\{1,5,2,4 \}\,</math>
-::<math>\{2,4\}\,</math>
-<math>\big |V^\prime \big| = </math> tamaño del nodo cover
 == Propiedades ==