El grafo Paley de orden 9, coloreado con tres colores, mostrando un clique de tres vértices. En este grafo y cada uno de sus subgrafos inducidos, el número cromático es igual al número de clique, por lo que es un grafo perfecto.
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 paper de 1963 publicado por Claude Berge. En este paper, 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.
Familias de grafos que son perfectos
Algunos de los grafos perfectos más conocidos son:
Grafos perfectamente ordenables (grafos que pueden ser ordenados de tal forma que una coloración voraz es óptima para cada subgrafo inducido)
Grafos de Meyniel (cada ciclo de largo impar mayor o igual a 5 tiene al menos 2 cuerdas)
Grafos trivialmente perfectos (en cada subgrafo inducido el tamaño del mayor conjunto independiente es igual al número de cliques maximales)
Grafos fuertemente perfectos (cada subgrafo inducido tiene un conjunto independiente que interseca todos sus cliques maximales)
Grafos muy fuertemente perfectos (en cada subgrafo inducido, cada vértice pertenece a un conjunto independiente llegando a todos los cliques maximales)
Caracterización y teoremas de grafos perfectos
La caracterización de los grafos perfectos fue un problema que llevó tiempo resolver. Un avance importante fue la respuesta afirmativa a la entonces conjetura de los grafos perfectos.
Un ciclo inducido de longitud impar mayor o igual a 5 es llamado agujero impar. Un subgrafo inducido complemento de un agujerio impar es llamado un antiagujero impar. Un grafo que no contiene agujeros impares ni sus complementos es llamado grafo de Berge. Como consecuencia del teorema de los grafos perfectos, un grafo perfecto es necesariamente un grafo de Berge, pero probar si lo inverso era cierto fue algo muy difícil. A esta afirmación difícil de probar se la conocía como la conjetura fuerte de los grafos perfectos, y finalmente pudo se probada afirmativamente en mayo de 2002.
Teorema fuerte de los grafos perfectos. (Chudnovsky, Robertson, Seymour, Thomas 2002)
Un grafo es perfecto si y sólo si es un grafo de Berge.
Como muchos otros resultados obtenido a partir de métodos estructurados, la prueba del teorema es larga y muy técnica. Los esfuerzos para resolver el problema permitieron avanzar en mayor profundidad la teoría de grafos, donde muchos problemas aún están abiertos. Por ejemplo, se pudo probar que el problema de reconocer grafos de Berge es co-NP (Lovász 1983), pero no se sabía si tenía o no complejidad P hasta que apareció la prueba del teorema fuerte de los grafos perfectos. Un algoritmo de tiempo polinómico fue descubierto poco después por Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, sin utilizar el teorema de los grafos perfectos.
Referencias
Berge, Claude (1961). «Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind». Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe10: 114.
Gallai, Tibor (1958). «Maximum-minimum Sätze über Graphen». Acta Math. Acad. Sci. Hungar.9: 395-434. doi:10.1007/BF02020271.
Golumbic, Martin Charles (1980), , Academic Press, ISBN 0-444-51530-5, archivado desde el original el 22 de mayo de 2010, consultado el 9 de enero de 2010.
Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988), Geometric Algorithms and Combinatorial Optimization, Springer-Verlag.
Lovász, László (1972). «Normal hypergraphs and the perfect graph conjecture». Discrete Mathematics2: 253-267. doi:10.1016/0012-365X(72)90006-4.
Lovász, László (1972). «A characterization of perfect graphs». Journal of Combinatorial Theory, Series B13: 95-98. doi:10.1016/0095-8956(72)90045-7.
Datos:Q1187620
Agosto 29, 2022
grafo, perfecto, teoría, grafos, grafo, perfecto, grafo, número, cromático, cada, subgrafo, inducido, igual, tamaño, mayor, clique, subgrafo, grafo, paley, orden, coloreado, tres, colores, mostrando, clique, tres, vértices, este, grafo, cada, subgrafos, induci. En teoria de grafos un grafo perfecto es un grafo en el que el numero cromatico de cada subgrafo inducido es igual al tamano del mayor clique de ese subgrafo El grafo Paley de orden 9 coloreado con tres colores mostrando un clique de tres vertices En este grafo y cada uno de sus subgrafos inducidos el numero cromatico es igual al numero de clique por lo que es un grafo perfecto En cualquier grafo el numero clique provee una cota inferior para el numero cromatico ya que a cada uno de los vertices en un clique se les debe asignar un color distinto para obtener una coloracion propia Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no solo para el grafo en si sino para todos los subgrafos inducidos En los grafos en general el numero cromatico y el numero de clique pueden ser distintos Por ejemplo un ciclo de 5 vertices requiere tres colores para obtener una coloracion correcta pero el clique mayor es de tamano dos Los grafos perfectos incluyen varias familias de grafos importantes y sirven para unificar resultados relacionados con la coloracion y los cliques en esas familias Por ejemplo en todos los grafos perfectos el problema de coloracion de grafos el problema de clique maximo y el problema del maximo conjunto independiente pueden ser resueltos en tiempo polinomico Grotschel Lovasz y Schrijver 1988 Ademas varios teoremas min max importantes de combinatoria como el teorema de Dilworth pueden ser expresados en terminos de la perfeccion de ciertos grafos asociados La teoria 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 tambien como un equivalente simple del teorema de Konig un resultado anterior que relaciona emparejamientos con cobertura de vertices en grafos bipartitos El primer uso de la frase grafo perfecto parece estar en un paper de 1963 publicado por Claude Berge En este paper Berge unio el resultado de Gallai con varios otros resultados similares definiendo los grafos perfectos y conjeturando una caracterizacion de esos grafos que luego fue probado como el Teorema fuerte de los grafos perfectos Familias de grafos que son perfectos EditarAlgunos de los grafos perfectos mas conocidos son Grafos bipartitos Los grafos adjuntos a grafos bipartitos ver Teorema de Konig Grafos de intervalos los vertices representan intervalos lineales las aristas las intersecciones de a pares no vacias Grafos cordales cada ciclo de cuatro o mas vertices tiene una cuerda que es una arista entre dos nodos que no son adyacentes dentro del ciclo Grafos con herencia de distancias las distancias entre vertices de un subgrafo inducido son las mismas que en el grafo original Grafos de permutaciones Grafos de comparabilidad un vertice por cada elemento en un orden parcial una arista entre cada par de elementos comparables Grafos Rueda con una cantidad impar de verticesGrafos perfectamente ordenables grafos que pueden ser ordenados de tal forma que una coloracion voraz es optima para cada subgrafo inducido Grafos de Meyniel cada ciclo de largo impar mayor o igual a 5 tiene al menos 2 cuerdas Grafos trivialmente perfectos en cada subgrafo inducido el tamano del mayor conjunto independiente es igual al numero de cliques maximales Grafos fuertemente perfectos cada subgrafo inducido tiene un conjunto independiente que interseca todos sus cliques maximales Grafos muy fuertemente perfectos en cada subgrafo inducido cada vertice pertenece a un conjunto independiente llegando a todos los cliques maximales Caracterizacion y teoremas de grafos perfectos EditarLa caracterizacion de los grafos perfectos fue un problema que llevo tiempo resolver Un avance importante fue la respuesta afirmativa a la entonces conjetura de los grafos perfectos Teorema de los grafos perfectos Lovasz 1972 Un grafo es perfecto si y solo si su complemento es tambien perfecto Un ciclo inducido de longitud impar mayor o igual a 5 es llamado agujero impar Un subgrafo inducido complemento de un agujerio impar es llamado un antiagujero impar Un grafo que no contiene agujeros impares ni sus complementos es llamado grafo de Berge Como consecuencia del teorema de los grafos perfectos un grafo perfecto es necesariamente un grafo de Berge pero probar si lo inverso era cierto fue algo muy dificil A esta afirmacion dificil de probar se la conocia como la conjetura fuerte de los grafos perfectos y finalmente pudo se probada afirmativamente en mayo de 2002 Teorema fuerte de los grafos perfectos Chudnovsky Robertson Seymour Thomas 2002 Un grafo es perfecto si y solo si es un grafo de Berge Como muchos otros resultados obtenido a partir de metodos estructurados la prueba del teorema es larga y muy tecnica Los esfuerzos para resolver el problema permitieron avanzar en mayor profundidad la teoria de grafos donde muchos problemas aun estan abiertos Por ejemplo se pudo probar que el problema de reconocer grafos de Berge es co NP Lovasz 1983 pero no se sabia si tenia o no complejidad P hasta que aparecio la prueba del teorema fuerte de los grafos perfectos Un algoritmo de tiempo polinomico fue descubierto poco despues por Chudnovsky Cornuejols Liu Seymour and Vuskovic sin utilizar el teorema de los grafos perfectos Referencias EditarBerge Claude 1961 Farbung von Graphen deren samtliche bzw deren ungerade Kreise starr sind Wiss Z Martin Luther Univ Halle Wittenberg Math Natur Reihe 10 114 Chudnovsky Maria Cornuejols Gerard Liu Xinming Seymour Paul Vuskovic Kristina 2005 Recognizing Berge graphs Combinatorica 25 143 186 doi 10 1007 s00493 005 0012 8 Chudnovsky Maria Robertson Neil Seymour Paul Thomas Robin 2006 The strong perfect graph theorem Annals of Mathematics 164 1 51 229 Gallai Tibor 1958 Maximum minimum Satze uber Graphen Acta Math Acad Sci Hungar 9 395 434 doi 10 1007 BF02020271 Golumbic Martin Charles 1980 Algorithmic Graph Theory and Perfect Graphs Academic Press ISBN 0 444 51530 5 archivado desde el original el 22 de mayo de 2010 consultado el 9 de enero de 2010 Grotschel Martin Lovasz Laszlo Schrijver Alexander 1988 Geometric Algorithms and Combinatorial Optimization Springer Verlag Lovasz Laszlo 1972 Normal hypergraphs and the perfect graph conjecture Discrete Mathematics 2 253 267 doi 10 1016 0012 365X 72 90006 4 Lovasz Laszlo 1972 A characterization of perfect graphs Journal of Combinatorial Theory Series B 13 95 98 doi 10 1016 0095 8956 72 90045 7 Datos Q1187620 Obtenido de https es wikipedia org w index php title Grafo perfecto amp oldid 120213168, wikipedia, wiki, leyendo, leer, libro, biblioteca,
