Coloración de grafos

Una vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible.

En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista talque aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.

El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo línea respectivo, y una coloración de caras de un grafo plano es una vértice coloración del grafo dual.

La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales es típicamente usado enteros no-negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colores pero no sobre cuales son.

Contenido

Historia

El primer resultado acerca de la coloración de grafos trataba exclusivamente sobre grafos planos y la coloración de mapas. Mientras intentaba colorear un mapa de Inglaterra, Francis Guthrie postulo la conjetura de los 4 colores, notando que 4 colores son suficientes para colorear el mapa tal que regiones que comparten un borde común no reciban el mismo color. El hermano de Guthrie pasa el problema a su profesor de matemáticas Augustus de Morgan en la universidad, mencionado en una carta a William Hamilton en 1852. Arthur Cayley raised el problema a la London Mathematical Society en 1879. algunos años después, Alfred Kempe publico un paper que resolvía el problema y por una década el problema de los 4 colores se considero resuelto. Por su contribución Kempe fue elegido Fellow de la Royal Society y posteriormente presidente de la London Mathematical Society.

En 1890, Heawood descubrió que el argumento de Kempe contenía un error, en ese paper el probo el teorema de los 5 colores, diciendo que cada mapa plano puede ser coloreado con a los más 5 colores, usando ideas de Kempe. En el siguiente siglo, teorías fueron desarrolladas para reducir el número de colores a cuatro, hasta que el teorema de los 4 colores fue finalmente probado en 1976 por Kenneth Appel y Wolfgang Haken.

La coloración de grafos han sido estudiada como un problema algorítmico desde 1970: el problema del número cromático es el problema 21 de Karp NP-completo de 1972, y aproximadamente al mismo tiempo varios algoritmos de tiempo exponencial fueron desarrollados basados en backtraking y en la eliminación y contracción de Zykov (1949). Uno de los mayores aplicaciones de la coloración de grafos, es la asignación de registros en compiladores introducida en 1981.

Archivo:Graph with all three-colourings.svg
Este grafo puede ser 3-coloreado de 12 formas diferentes.

Definiciones y terminología

Vértice coloración

La vértice coloración (o simplemente coloración) es la asignación de los vértices de un grafo con colores tal que dos vértices que compartan la misma arista tengan colores diferentes. Un grafo con loops no puede ser coloreado, y solo se consideran grafos sin loops.

La terminología de usar colores para etiquetar vértices proviene del problema de colorear mapas. Las etiquetas como rojo o azul son solamente utilizadas cuando el número de colores es pequeño, y normalmente los colores están representados por los enteros {1, 2, 3, …}.

Una coloración que usa a lo más k colores se llama k-coloración (propia). El menor número de colores necesarios para colorear un grafo G se denota número cromático . Un grafo que puede ser asignada una k-coloración (propia) es k-coloreable y es k-cromático si su número cromático es exactamente k. Un subconjunto de vértices asignados con el mismo color se llama una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-coloración es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partito y k-coloreable tienen el mismo significado.

Polinomio cromático

Archivo:Chromatic polynomial of all 3-vertex graphs.png
Todos los grafos no-isomorfos de 3 vértices y sus polinomios cromáticos. El grafo vació E3 (rojo) admite una 1-coloración. El grafo verde admite 12 coloraciones con 3 colores.

El polinomio cromático cuenta el número de maneras en las cuales puede ser coloreado un grafo usando no más que un número de colores dado. Por ejemplo, usando 3 colores, el grafo en la imagen de la derecha puede ser coloreado de 12 formas distintas. Con solo 2 colores, no puede ser coloreado. Con 4 colores, puede ser coloreado de 24+4*12 maneras distintas: usando los cuatro colores juntos, hay 4!= 24 coloraciones validas (toda asignación de cuatro colores a algún grafo de cuatro vértices es una coloración propia); y para cada elección de tres de los cuatro colores, hay 12 3-coloraciones validas. Así que, para el grafo del ejemplo, una tabla de números de coloraciones validas puede comenzar como esta:

Colores disponibles 1 2 3 4
Número de coloraciones 0 0 12 72

El polinomio cromático es una función p(G, t) que cuenta el número de t-coloraciones de G. como el nombre lo indica para un grafo G la función es un polinomio en t. para el grafo del ejemplo, P(G, t)= t(t-1)2 (t-2) y P(G,4)=72

Polinomios cromáticos de algunos grafos.
Triángulo K3 t(t-1)(t-2) \,
Grafo completo Kn t(t-1)(t-2) \cdots (t-(n-1))\,
Árbol con n vértices t(t-1)^{n-1}\,
Ciclo Cn (t-1)^n+(-1)^n(t-1)\,
Grafo de Petersen t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)\,

Arista coloración

Una arista coloración de un grafo, es una coloración de las aristas, denotada como la asignación de colores a aristas tal que aristas incidentes tengan un color distinto. Una arista coloración con k colores es llamada k-arista-coloración y es equivalente al problema de particionar el conjunto de aristas en k emparejamientos. El menor número de colores necesarios para un arista coloración de un grafo G es el índice cromático o número cromático de aristas. Una coloración Tait es una 3-arista-coloración de un grafo cúbico. El teorema de los cuatro colores es equivalente a que cada grafo cúbico sin puentes admite una coloración Tait.

Propiedades

Cotas del número cromático

Asignando distintos colores a distintos vértices siempre obtendremos una coloración propia, entonces

1 \le \chi(G) \le n.\,

El único grafo que es 1-coloreable es el grafo sin aristas, y el grafo completo K_n \, de n vértices requiere \chi(K_n)=n \, colores.

Si G contiene un clique de orden k, entonces a lo menos son necesarios k colores para colorear el clique; en otras palabras, el número cromático es a los menos el número de clique:

\chi(G) \ge \omega(G).\,

Los grafos 2-coloreables son exactamente grafos bipartitos, incluidos árboles y bosques. Por el teorema de los cuatro colores, todo grafo plano es 4-coloreable.

Una coloración a través de un algoritmo voraz muestra que cada grafo puede ser coloreado con un color más que el grado del vértice máximo.

\chi(G) \le \Delta(G) + 1. \,

Cotas del índice cromático

La arista coloración es una vértice coloración de su grafo lineal, y viceversa. Esto es,

\chi'(G)=\chi(L(G)). \,

Existe un fuerte relación entre la arista coloración y el grado máximo del grafo. Como todas las aristas incidentes a algún vértice necesitan colores distintos, tenemos

\chi'(G) \ge \Delta(G).\,

Más aún,

Teorema de König: Si G \, es bipartito entonces \chi'(G) = \Delta(G) \,

Otras coloraciones

Teoría de Ramsey

Artículo principal: Teoría de Ramsey

Una importante clase de problemas de coloreado impropias es estudiada en teoría de Ramsey, en donde se asignan colores a las aristas del grafo, y no hay restricción sobre los colores en aristas incidentes. Un ejemplo simple es el teorema de la amistad que nos dice que en toda 2-arista-coloración del grafo completo de seis vértices habrá un triángulo monocromático; extrapolando se puede interpretar que de un grupo de seis personas siempre hay tres que se conocen mutuamente o tres que no se conocen mutuamente. La teoría de Ramsey estudia la generalización de esta idea para encontrar regularidad en el aparente desorden, e identificar condiciones generales para la existencia de subgrafos monocromáticos con alguna estructura dada.


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • 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… …   Wikipedia Español

  • Grafo etiquetado — En matemáticas, en la disciplina de teoría de grafos, un grafo etiquetado es la asignación de etiquetas, tradicionalmente representada mediante enteros, a las aristas or vértices, o ambos, de un grafo.[1] Formalmente, dado un grafo G, un vértice… …   Wikipedia Español

  • Teorema de la amistad — Los 78 grafos posibles de amigos extraños con 6 vértices. En cada grafo, las aristas de color azul/rojo muestran la relación mutua de amigos/extraños. El teorema de amigos y extraños o teorema de la amistad es un teorema en el campo matemático… …   Wikipedia Español

  • Problema de la cobertura de vértices — Saltar a navegación, búsqueda En ciencias de la computación, el Problema de la cobertura de vértices es un problema NP completo, que pertenece a los 21 problemas NP completos de Karp. Es muy utilizado en teoría de complejidad computacional para… …   Wikipedia Español

  • Teorema de los cuatro colores — Ejemplo de mapa coloreado con cuatro colores. Mapa …   Wikipedia Español

  • Lista de 21 problemas NP-completos de Karp — Por Lista de 21 problemas NP completos de Karp se entiende a una lista de 21 problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de …   Wikipedia Español

  • Problema de satisfacibilidad booleana — Saltar a navegación, búsqueda En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde… …   Wikipedia Español


Compartir el artículo y extractos

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

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.