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