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értices (o arcos) cuyos elementos son ''cerrados'' ([[grafo|adyacentes]]) a todos los arcos (o vértices) 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 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 [[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értice]]s <math>V\,</math> en los que cada [[arco]] de <math>G\,</math> [[grado|incide]] al menos en un nodo de <math>V\,</math>. El '''mínimo nodo covering''' es el más pequeño node cover. Llamamos <math>V\,</math> ''covers'' a los arcos 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 node 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 node 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 sus vértices (arcos) es trivialmente un node 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 20: @@
 == Véase también ==
-[[Problema de la clique]]
+* [[Cobertura de aristas]]
+* [[Problema de la cobertura de vértices]]
+* [[Problema de la clique]]
 == Referencias ==
 * 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:Knotenüberdeckung]]
-[[en:Covering (graph theory)]]
-[[he:כיסוי (תורת הגרפים)]]
-[[pl:Pokrycie wierzchołkowe]]