Cobertura de vértices

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 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

grafo G
  • 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

Véase también

Referencias

  • Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Problema de la cobertura de vértices — Saltar a navegación, búsqueda En ciencias de la computación, el Problema de la cobertura de vértices es un problema NP completo, que pertenece a los 21 problemas NP completos de Karp. Es muy utilizado en teoría de complejidad computacional para… …   Wikipedia Español

  • Cobertura de aristas — En teoría de Grafos , una covertura de aristas de un grafo es un conjunto de aristas donde cada vertice del grafo es incidente en al menos en una arista del conjunto. En ciencias de la computación, el problema de la cobertura mínima de arista es… …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • Vértice (teoría de grafos) — Para otros usos de este término, véase vértice. Un grafo con 6 vértices y 7 aristas. En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de… …   Wikipedia Español

  • Grafo perfecto — El grafo Paley de orden 9, coloreado con tres colores, mostrando un clique de tres vértices. En este grafo y cada uno de sus subgrafos inducidos, el número cromático es igual al número de clique, por lo que es un grafo perfecto. En teoría de… …   Wikipedia Español

  • Conjunto independiente — El (inesperadamente asimétrico) conjunto de 9 vértices azules es un conjunto independiente maximal para este grafo de 24 vértices. En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno es… …   Wikipedia Español

  • Reducción (complejidad) — Saltar a navegación, búsqueda Ejemplo de reducción de un problema de satisfacibilidad booleana a un problema de cobertura de vértices. Los vértices azules forman una cobertura que se corresponde con los valores verdaderos. En teoría de la… …   Wikipedia Español

  • Lista de 21 problemas NP-completos de Karp — Por Lista de 21 problemas NP completos de Karp se entiende a una lista de 21 problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de …   Wikipedia Español

  • Algoritmo de aproximación — En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP hard; como es poco… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”