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 19:24 11 ene 2010

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.

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

Un arco covering para un grafo $G\,$ es un conjunto de arcos $E\,$ en los que cada nodo de $G\,$ es adyacente al menos a un arco de $E\,$ . El mínimo arco covering es el menor arco covering. Llamamos $E\,$ covers a los vértices 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 hace referencia normalmente al nodo covering.

Ejemplos

para cualquier grafo $G\,$ el conjunto de todos sus vértices (arcos) es trivialmente un nodo 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=(V,E)\,$ no orientado y conexo. $V\subseteq \;V^{\prime }$ es un nodo cover si $\forall e\in \ E$ al menos uno de los puntos finales de $e\,$ finaliza en $V^{\prime }\,$

ejemplos:

\{1,5,2,4\}\,

\{2,4\}\,

${\big |}V^{\prime }{\big |}=$ tamaño del nodo cover

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: @@
-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.
+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.
-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 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 [[conjunto independiente|conjuntos independientes]] y [[matching]]s.
@@ Línea 10: / Línea 10: @@
 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.
-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.
+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.
-Cuando se habla de '''covering''' se refiere normalmente al nodo covering.
+Cuando se habla de '''covering''' se hace referencia normalmente al ''nodo covering''.
 == Ejemplos ==