Metraipolis › archive › dc_2f9dfb79c985
Grafo perfecto — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Grafo_perfecto
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T12:51:05.332Z
- SHA-256 of the archived text
634264f27e5266459e00d6262f4d5de1be0672976d782f93e4fda4e86084ef3b- Stable URL of this page
https://metraipolis.com/documento/dc_2f9dfb79c985
How to cite
Grafo perfecto — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Grafo_perfecto (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2f9dfb79c985 (Metraipolis archive dc_2f9dfb79c985, sha256 634264f27e5266459e00d6262f4d5de1be0672976d782f93e4fda4e86084ef3b)
BibTeX
@misc{dc2f9dfb79c985,
title = {Grafo perfecto — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Grafo_perfecto},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2f9dfb79c985; sha256 634264f27e5266459e00d6262f4d5de1be0672976d782f93e4fda4e86084ef3b},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Grafo_perfecto. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. Los grafos perfectos incluyen varias familias de grafos importantes, y sirven para unificar resultados relacionados con la coloración y los cliques en esas familias. Por ejemplo, en todos los grafos perfectos, el problema de coloración de grafos, el problema de clique máximo y el problema del máximo conjunto independiente pueden ser resueltos en tiempo polinómico (Grötschel, Lovász y Schrijver, 1988). Además, varios teoremas min-max importantes de combinatoria como el teorema de Dilworth, pueden ser expresados en términos de la perfección de ciertos grafos asociados. La teoría de grafos perfectos fue desarrollada a partir de un resultado obtenido en 1958 por Tibor Gallai que en lenguaje moderno puede ser interpretado de modo que el complementario de un grafo bipartito es perfecto. Este resultado puede ser visto también como un equivalente simple del teorema de König, un resultado anterior que relaciona emparejamientos con cobertura de vértices en grafos bipartitos. El primer uso de la frase "grafo perfecto" parece estar en un artículo de 1963 publicado por Claude Berge. En este artículo, Berge unió el resultado de Gallai con varios otros resultados similares, definiendo los grafos perfectos y conjeturando una caracterización de esos grafos que luego fue probado como el Teorema fuerte de los grafos perfectos. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»). Fonte: Wikipedia in spagnolo, voce «Grafo perfecto» — https://es.wikipedia.org/wiki/Grafo_perfecto Wikidata Q1187620 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1187620 Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Grafo_perfecto?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 171113851, consultata il 2026-10-07T12:21:37.846Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 95a5cdfa5e40a692f6e7596b3db65722a187814a9456eca9afc187704015630b