Diferencia entre revisiones de «Cobertura de vértices»

Contenido eliminado Contenido añadido

En renglón

Revisión actual - 10:44 3 jul 2022

Ejemplos de coberturas de vértices (conformadas por los vértices en rojo).

Ejemplos de coberturas de vértices mínimas.

En la disciplina matemática de la teoría de grafos, una cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada arista del grafo es incidente a al menos un vértice del conjunto.

El problema de encontrar la menor cobertura de vértices en un grafo se denomina problema de la cobertura de vértices. En teoría de la complejidad computacional se ha demostrado que este es un problema 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.

Ejemplos

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

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.

Datos: Q11515519

@@ 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 la disciplina [[matemáticas|matemática]] de la [[teoría de grafos]], una '''cobertura de vértices''' (en inglés, '''''vertex cover''''') o simplemente '''cobertura''' de un [[grafo]], es un conjunto de [[vértice (teoría de grafos)|vértices]] tales que cada [[Arista (teoría de grafos)|arista]] del grafo es incidente a al menos un vértice del conjunto.
+El problema de encontrar la menor cobertura de vértices en un grafo se denomina [[problema de la cobertura de vértices]]. En [[teoría de la complejidad computacional]] se ha demostrado que este es un problema [[NP-completo]].
-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 [[conjunto independiente|conjuntos independientes]] y [[matching]]s.
+La cobertura de vértices y [[cobertura de aristas|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> son adyacentes 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 vertices 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.
-Cuando se habla de '''covering''' se refiere normalmente al nodo covering.
 == Ejemplos ==
+* Para cualquier grafo, el conjunto de todos sus vértices es trivialmente una cobertura de vértices.
-[[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 ==
@@ Línea 34: / Línea 21: @@
 == Véase también ==
+* [[Cobertura de aristas]]
 * [[Problema de la cobertura de vértices]]
 * [[Problema de la clique]]
@@ Línea 40: / Línea 28: @@
 * Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. '''2''', 133-138, 1959.
+{{Control de autoridades}}
-[[Categoría:Teoría de grafos]]
+[[Categoría:Operaciones en grafos]]
 [[Categoría:Optimización]]
-[[Categoría:Investigación Operativa]]
+[[Categoría:Investigación operativa]]
+[[Categoría:Invariantes de grafos]]
-[[de:Glossar Graphentheorie#Knotenüberdeckung]]
-[[en:Vertex cover problem]]
-[[fr:Problème de couverture de sommets]]
-[[he:בעיית כיסוי קודקודים]]
-[[it:Vertex cover problem]]
-[[ja:頂点被覆問題]]
-[[ru:Задача о вершинном покрытии]]