En teoría de grafos , el teorema de grafos perfectos de László Lovász ( 1972a , 1972b ) establece que un grafo no dirigido es perfecto si y solo si su grafo de complemento también es perfecto. Este resultado había sido conjeturado por Berge ( 1961 , 1963 ), y a veces se le llama el teorema del grafo perfecto débil para distinguirlo del teorema del grafo perfecto fuerte [1] que caracteriza a los grafos perfectos por sus subgrafos inducidos prohibidos .
Declaración
Un gráfico perfecto es un gráfico no dirigido con la propiedad de que, en cada uno de sus subgrafos inducidos , el tamaño de la camarilla más grande es igual al número mínimo de colores en una coloración del subgrafo. Los gráficos perfectos incluyen muchas clases de gráficos importantes, incluidos gráficos bipartitos , gráficos de cuerdas y gráficos de comparabilidad .
El complemento de un gráfico tiene un borde entre dos vértices si y solo si el gráfico original no tiene un borde entre los mismos dos vértices. Por lo tanto, una camarilla en el gráfico original se convierte en un conjunto independiente en el complemento y una coloración de la gráfica original se convierte en una cubierta de camarilla del complemento.
El teorema del gráfico perfecto establece:
- El complemento de una gráfica perfecta es perfecto.
De manera equivalente, en un gráfico perfecto, el tamaño del conjunto máximo independiente es igual al número mínimo de camarillas en una portada de camarillas.
Ejemplo
Sea G un gráfico de ciclo de longitud impar mayor que tres (un llamado "agujero impar"). Entonces G requiere al menos tres colores en cualquier color, pero no tiene triángulo, por lo que no es perfecto. Por el teorema del gráfico perfecto, el complemento de G (un "anti-agujero impar") tampoco debe ser perfecto. Si G es un ciclo de cinco vértices, es isomorfo a su complemento , pero esta propiedad no es cierta para ciclos impares más largos, y no es tan trivial calcular el número de camarilla y el número cromático en un anti-agujero impar como lo es en un agujero extraño. Como establece el teorema del grafo perfecto fuerte , los agujeros impares y los antiholes impares resultan ser los subgrafos inducidos prohibidos mínimos para los gráficos perfectos.
Aplicaciones
En un gráfico bipartito no trivial , el número óptimo de colores es (por definición) dos, y (dado que los gráficos bipartitos no tienen triángulos ) el tamaño máximo de la camarilla también es dos. Además, cualquier subgrafo inducido de un gráfico bipartito permanece bipartito. Por tanto, los gráficos bipartitos son perfectos. En los gráficos bipartitos de n -vértices, una cobertura mínima de clique toma la forma de un emparejamiento máximo junto con un clique adicional por cada vértice no emparejado , con tamaño n - M , donde M es la cardinalidad del emparejamiento. Así, en este caso, el teorema del grafo perfecto implica el teorema de Kőnig de que el tamaño de un conjunto máximo independiente en un grafo bipartito también es n - M , [2] un resultado que fue una gran inspiración para la formulación de Berge de la teoría de grafos perfectos. .
El teorema de Mirsky que caracteriza la altura de un conjunto parcialmente ordenado en términos de particiones en antichains puede formularse como la perfección del gráfico de comparabilidad del conjunto parcialmente ordenado, y el teorema de Dilworth que caracteriza el ancho de un conjunto parcialmente ordenado en términos de particiones en cadenas puede formularse como la perfección de los complementos de estos gráficos. Por lo tanto, el teorema del gráfico perfecto se puede usar para probar el teorema de Dilworth a partir de la prueba (mucho más fácil) del teorema de Mirsky, o viceversa. [3]
Prueba de Lovász
Para probar el teorema del grafo perfecto, Lovász usó una operación de reemplazo de vértices en un grafo por camarillas; Berge ya sabía que, si una gráfica es perfecta, la gráfica formada por este proceso de reemplazo también es perfecta. [4] Cualquier proceso de reemplazo de este tipo puede dividirse en pasos repetidos de duplicar un vértice. Si el vértice duplicado pertenece a una camarilla máxima del gráfico, aumenta tanto el número de camarilla como el número cromático en uno. Si, por otro lado, el vértice duplicado no pertenece a una camarilla máxima, forme un gráfico H eliminando los vértices con el mismo color que el vértice duplicado (pero no el vértice duplicado en sí) de una coloración óptima del gráfico dado . Los vértices eliminados se encuentran con cada camarilla máxima, por lo que H tiene un número de camarilla y un número cromático uno menos que el del gráfico dado. Los vértices eliminados y la nueva copia del vértice duplicado se pueden agregar nuevamente como una clase de un solo color, lo que muestra que en este caso el paso de duplicación deja el número cromático sin cambios. El mismo argumento muestra que la duplicación conserva la igualdad del número de clique y el número cromático en cada subgrafo inducido del gráfico dado, por lo que cada paso de duplicación preserva la perfección del gráfico. [5]
Dado un gráfico perfecto G , Lovász forma un gráfico G * reemplazando cada vértice v por una camarilla de t v vértices, donde t v es el número de conjuntos independientes máximos distintos en G que contienen v . Es posible corresponder cada uno de los conjuntos máximos independientes distintos en G con uno de los conjuntos máximos independientes en G *, de tal manera que los conjuntos máximos independientes elegidos en G * sean todos disjuntos y cada vértice de G * aparezca en un conjunto único elegido; es decir, G * tiene un color en el que cada clase de color es un conjunto máximo independiente. Necesariamente, esta coloración es una coloración óptima de G *. Debido a que G es perfecto, también lo es G *, y por lo tanto tiene una camarilla máxima K * cuyo tamaño es igual al número de colores en esta coloración, que es el número de conjuntos independientes máximos distintos en G ; necesariamente, K * contiene un representante distinto para cada uno de estos conjuntos máximos independientes. El correspondiente conjunto K de vértices en G (los vértices cuya expandido camarillas en G * de intersección K *) es un clique en G con la propiedad de que se cruza cada conjunto máximo independiente en G . Por lo tanto, el gráfico formado a partir de G eliminando K tiene un número de cobertura de clique como máximo uno menos que el número de clique de G y un número de independencia al menos uno menos que el número de independencia de G , y el resultado sigue por inducción sobre este número. [6]
Relación con el teorema del grafo perfecto fuerte
El teorema del grafo perfecto fuerte de Chudnovsky et al. (2006) establece que un gráfico es perfecto si y solo si ninguno de sus subgrafos inducidos son ciclos de longitud impar mayor o igual a cinco, o sus complementos. Debido a que esta caracterización no se ve afectada por la complementación de grafos, inmediatamente implica el teorema del grafo perfecto débil.
Generalizaciones
Cameron, Edmonds & Lovász (1986) demostraron que, si los bordes de un grafo completo se dividen en tres subgrafos de tal manera que cada tres vértices inducen un grafo conectado en uno de los tres subgrafos, y si dos de los subgrafos son perfectos , entonces el tercer subgrafo también es perfecto. El teorema del gráfico perfecto es el caso especial de este resultado cuando uno de los tres subgrafos es el gráfico vacío .
Notas
- ↑ Berge también conjeturó esto, pero Chudnovsky et al. (2006) .
- ↑ Kőnig (1931) , redescubierto más tarde por Gallai (1958) .
- ^ Golumbic (1980) , Sección 5.7, "Colorear y otros problemas en gráficos de comparabilidad", págs. 132-135.
- ^ Véase Golumbic (1980) , Lemma 3.1 (i) y Reed (2001) , Corolario 2.21.
- ^ Reed (2001) , Lema 2.20.
- ^ Seguimos aquí la exposición de la prueba de Reed (2001) . Golumbic (1980) señala que gran parte de esta línea de razonamiento fue rápidamente reconstruida por DR Fulkerson después de escuchar el resultado de Lovász pero no ver su prueba.
Referencias
- Berge, Claude (1961), "Färbung von Graphen, deren deren sämtliche beziehungsweise ungerade Kreise Starr sind", Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche Reihe (en alemán), 10 : 114.
- Berge, Claude (1963), "Gráficos perfectos", Seis artículos sobre teoría de gráficos , Calcuta: Instituto de Estadística de la India, págs. 1–21..
- Cameron, K .; Edmonds, J .; Lovász, L. (1986), "Una nota sobre gráficos perfectos", Periodica Mathematica Hungarica , 17 (3): 173-175, doi : 10.1007 / BF01848646 , MR 0859346.
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del gráfico fuerte perfecto", Annals of Mathematics , 164 (1): 51-229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51 , MR 2233847.
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2003), "Progress on perfect graphs" (PDF) , Programación matemática , Serie B., 97 (1–2): 405–422, doi : 10.1007 / s10107-003-0449-8 , MR 2004404.
- Gallai, Tibor (1958), "Máximo-mínimo Sätze über Graphen", Acta Mathematica Academiae Scientiarum Hungaricae (en alemán), 9 (3–4): 395–434, doi : 10.1007 / BF02020271 , MR 0124238
- Golumbic, Martin Charles (1980), "3.2. El teorema del gráfico perfecto", Teoría algorítmica del gráfico y gráficos perfectos , Nueva York: Academic Press, págs. 53–58, ISBN 0-12-289260-7, MR 0562306.
- Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok (en húngaro), 38 : 116-119
- Lovász, László (1972a), "Hipergrafías normales y la conjetura de la gráfica perfecta", Matemáticas discretas , 2 (3): 253-267, doi : 10.1016 / 0012-365X (72) 90006-4.
- Lovász, László (1972b), "Una caracterización de gráficos perfectos", Journal of Combinatorial Theory , Serie B, 13 (2): 95–98, doi : 10.1016 / 0095-8956 (72) 90045-7.
- Reed, Bruce A. (2001), "De la conjetura al teorema", en Ramírez Alfonsín, Jorge L .; Reed, Bruce A. (eds.), Perfect Graphs , Serie Wiley-Interscience sobre Matemáticas Discretas y Optimización, Chichester: Wiley, págs. 13-24, MR 1861356.