Metraipolis › archive › dc_30780548290e
Grafo bien cubierto — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Grafo_bien_cubierto
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-31T08:34:42.242Z
- SHA-256 of the archived text
f6107837fa3eb5a9338a94e872db3ea85b1a113ba267bfe4e0f430fee46d0cfc- Stable URL of this page
https://metraipolis.com/documento/dc_30780548290e
How to cite
Grafo bien cubierto — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Grafo_bien_cubierto (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_30780548290e (Metraipolis archive dc_30780548290e, sha256 f6107837fa3eb5a9338a94e872db3ea85b1a113ba267bfe4e0f430fee46d0cfc)
BibTeX
@misc{dc30780548290e,
title = {Grafo bien cubierto — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Grafo_bien_cubierto},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_30780548290e; sha256 f6107837fa3eb5a9338a94e872db3ea85b1a113ba267bfe4e0f430fee46d0cfc},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Grafo_bien_cubierto. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En teoría de grafos, un grafo bien cubierto (en inglés, well-covered graph) es un grafo no dirigido en el que todas las coberturas de vértices minimales tienen el mismo tamaño. Aquí, una cobertura de vértices es un conjunto de vértices que toca todas las aristas, y es minimal si al quitarle cualquier vértice alguna arista queda sin cubrir. De forma equivalente, los grafos bien cubiertos son aquellos en los que todos los conjuntos independientes maximales tienen el mismo tamaño. Michael D. Plummer definió y estudió por primera vez los grafos bien cubiertos en 1970. Entre los grafos bien cubiertos se encuentran todos los grafos completos, los grafos bipartitos completos equilibrados y los grafos de la torre, cuyos vértices representan las casillas de un tablero de ajedrez y cuyas aristas representan los movimientos de una torre. Las caracterizaciones conocidas de los grafos cúbicos bien cubiertos, de los grafos sin garras bien cubiertos y de los grafos bien cubiertos de cintura grande permiten reconocer estos grafos en tiempo polinómico, pero comprobar si otros tipos de grafos son bien cubiertos es un problema co-NP-completo. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»). Fonte: Wikipedia in spagnolo, voce «Grafo bien cubierto» — https://es.wikipedia.org/wiki/Grafo_bien_cubierto Wikidata Q7981049: «graph with equal-size maximal independent sets» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7981049 Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Grafo_bien_cubierto?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 176048935, consultata il 2026-10-31T08:23:59.833Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 30990fbb31689eb5aacb32f2d85e7874c29cc591c04173444d9b33431e2277f6