Grafo perfecto

Grafo perfecto
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 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 correcta. 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 polinomial (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 grafo complemento 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 bipartitos
  • Los grafos adjuntos a grafos bipartitos (ver Teorema de König)
  • Grafos de intervalos (los vértices representan intervalos lineales, las aristas las intersecciones de a pares no vacías)
  • Grafos cordales (cada ciclo de cuatro o más vértices 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 vértices de un subgrafo inducido son las mismas que en el grafo original)
  • Grafos de permutaciones
  • Grafos de comparabilidad (un vértice por cada elemento en un orden parcial, una arista entre cada par de elementos comparables)
  • Grafos Rueda con una cantidad impar de vértices
  • 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.

Teorema de los grafos perfectos. (Lovász 1972)

Un grafo es perfecto si y sólo si su complemento es también 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 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 polinomial fue descubierto poco después por Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, sin utilizar el teorema de los grafos perfectos.


Referencias


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Grafo umbral — Un ejemplo de grafo umbral. En teoría de grafos, un grafo umbral (mejor conocido en inglés como threshold graph) es un grafo que puede ser construido desde un único vértice aplicando repetidamente cualquiera de las siguientes dos operaciones:… …   Wikipedia Español

  • Cuadrado perfecto — Un número cuadrado perfecto en matemáticas, o un número cuadrado, es un número entero que es el cuadrado de algún otro; dicho de otro modo, un número cuya raíz cuadrada es un número entero. Por ejemplo, 9 es un número cuadrado perfecto ya que… …   Wikipedia Español

  • László Lovász — Nacimiento 9 de marzo de 1948 Budapest …   Wikipedia Español

  • Matching — Saltar a navegación, búsqueda En matemática discreta y en particular en la teoría de grafos, un matching o conjunto independiente de aristas (también llamado emparejamiento o apareamiento) en un grafo es un conjunto de aristas independientes, es… …   Wikipedia Español

  • Apareamiento (teoría de gráficas) — En matemática discreta y en particular en la teoría de grafos, un apareamiento o conjunto independiente de aristas, también llamado emparejamiento o matching (en inglés), en un grafo es un conjunto de aristas independientes, es decir, sin… …   Wikipedia Español

  • Matriz de adyacencia — La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias. Contenido 1 Construcción de la matriz a partir de un grafo 1.1 Ejemplo de grafo no dirigido 1.2 Ejemplo de grafo dir …   Wikipedia Español

  • Árbol binario — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Cobertura de aristas — En teoría de Grafos , una covertura de aristas de un grafo es un conjunto de aristas donde cada vertice del grafo es incidente en al menos en una arista del conjunto. En ciencias de la computación, el problema de la cobertura mínima de arista es… …   Wikipedia Español

  • Algoritmo Húngaro — Saltar a navegación, búsqueda EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue… …   Wikipedia Español

  • Algoritmo húngaro — EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”