Metraipolis › archive › dc_043306abcc79

Cobertura de vértices — Wikipedia (es)

Source
Wikipedia (es)
Original
https://es.wikipedia.org/wiki/Cobertura_de_v%C3%A9rtices
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T17:12:57.893Z
SHA-256 of the archived text
a3095f46d86eb514d721748586375593b67ad1802f4691069e0c8b0eac56573f
Stable URL of this page
https://metraipolis.com/documento/dc_043306abcc79

How to cite

Cobertura de vértices — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Cobertura_de_v%C3%A9rtices (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_043306abcc79 (Metraipolis archive dc_043306abcc79, sha256 a3095f46d86eb514d721748586375593b67ad1802f4691069e0c8b0eac56573f)
BibTeX
@misc{dc043306abcc79,
  title = {Cobertura de vértices — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Cobertura_de_v%C3%A9rtices},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_043306abcc79; sha256 a3095f46d86eb514d721748586375593b67ad1802f4691069e0c8b0eac56573f},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Cobertura_de_v%C3%A9rtices. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En teoría de grafos, una cobertura de vértices (a veces, cobertura de nodos) de un grafo es un conjunto de vértices que incluye al menos un extremo de cada arista del grafo. En ciencias de la computación, el problema de encontrar una cobertura mínima de vértices es un problema de optimización clásico. Es NP-difícil, por lo que no puede resolverse con un algoritmo de tiempo polinómico si P ≠ NP. Además, es difícil de aproximar: no puede aproximarse hasta un factor menor que 2 si la conjetura del juego único es verdadera. Por otro lado, tiene varias aproximaciones simples de 2 factores. Es un ejemplo típico de un problema de optimización NP-difícil que tiene un algoritmo de aproximación. Su versión de decisión, el problema de cobertura de vértices, fue uno de los veintiún problemas NP-completos de Karp y, por lo tanto, es un problema clásico NP-completo en teoría de la complejidad computacional. Además, el problema de cobertura de vértices es manejable con parámetros fijos y un problema central en la teoría de la complejidad parametrizada. El problema de cobertura mínima de vértices puede formularse como un caso de programación lineal semi entero, cuyo programa lineal dual es el problema de máxima coincidencia. Los problemas de cobertura de vértices se han generalizado a los hipergrafos; véase cubiertas de vértice en hipergrafos.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»).
Fonte: Wikipedia in spagnolo, voce «Cobertura de vértices» — https://es.wikipedia.org/wiki/Cobertura_de_v%C3%A9rtices
Wikidata Q11515519: «a set of vertices that includes at least one endpoint of every edge in a graph» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q11515519
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Cobertura_de_v%C3%A9rtices?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 172717471, consultata il 2026-10-07T16:44:04.865Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: c3d6b51005c2cdddb39b01f641b45dce9fa7d30c8b89e2cb7072962c89a8e59e