Coloración de gráficos

En teoría de grafos, la coloración de gráficos es un caso especial de etiquetado de gráficos; se trata de una asignación de etiquetas tradicionalmente llamadas "colores" a elementos de un gráfico sujetos a ciertas restricciones. En su forma más simple, es una forma de colorear los vértices de un gráfico de modo que no haya dos vértices adyacentes del mismo color; esto se llama coloración de vértices. De manera similar, una coloración de bordes asigna un color a cada borde para que no haya dos bordes adyacentes del mismo color, y una coloración de caras de un gráfico plano asigna un color a cada uno. cara o región para que no haya dos caras que compartan un límite que tengan el mismo color.

La coloración de vértices se utiliza a menudo para introducir problemas de coloración de gráficos, ya que otros problemas de coloración se pueden transformar en una instancia de coloración de vértices. Por ejemplo, una coloración de borde de un gráfico es solo una coloración de vértice de su gráfico lineal, y una coloración de cara de un gráfico plano es solo una coloración de vértice de su dual. Sin embargo, los problemas de coloración que no son de vértices a menudo se plantean y estudian tal cual. Esto es en parte pedagógico y en parte porque algunos problemas se estudian mejor en su forma sin vértice, como en el caso de la coloración de bordes.

La convención de usar colores tiene su origen en colorear los países de un mapa, donde cada cara está literalmente coloreada. Esto se generalizó para colorear las caras de un gráfico incrustado en el plano. Por dualidad plana pasó a colorear los vértices y de esta forma se generaliza a todos los gráficos. En representaciones matemáticas e informáticas, es típico utilizar los primeros números enteros positivos o no negativos como "colores". En general, se puede utilizar cualquier conjunto finito como "conjunto de colores". La naturaleza del problema de coloración depende de la cantidad de colores pero no de cuáles son.

La coloración de gráficos tiene muchas aplicaciones prácticas, así como desafíos teóricos. Además de los tipos de problemas clásicos, también se pueden establecer diferentes limitaciones en el gráfico, en la forma de asignar un color o incluso en el color mismo. Incluso ha alcanzado popularidad entre el público en general en forma del popular rompecabezas numérico Sudoku. La coloración de gráficos sigue siendo un campo de investigación muy activo.

Nota: muchos de los términos utilizados en este artículo se definen en el Glosario de teoría de grafos.

Historia

Los primeros resultados sobre la coloración de gráficos tratan casi exclusivamente de gráficos planos en forma de coloración de mapas. Mientras intentaba colorear un mapa de los condados de Inglaterra, Francis Guthrie postuló la conjetura de los cuatro colores, señalando que cuatro colores eran suficientes para colorear el mapa de modo que ninguna región que compartiera una frontera común recibiera el mismo color. El hermano de Guthrie transmitió la cuestión a su profesor de matemáticas Augustus De Morgan en el University College, quien la mencionó en una carta a William Hamilton en 1852. Arthur Cayley planteó el problema en una reunión de la Sociedad Matemática de Londres en 1879. Ese mismo año, Alfred Kempe publicó un artículo que pretendía establecer el resultado, y durante una década se consideró resuelto el problema de los cuatro colores. Por su logro, Kempe fue elegido miembro de la Royal Society y más tarde presidente de la London Mathematical Society.

En 1890, Percy John Heawood señaló que el argumento de Kempe era incorrecto. Sin embargo, en ese artículo demostró el teorema de los cinco colores, diciendo que cada mapa plano se puede colorear con no más de cinco colores, usando ideas de Kempe. En el siglo siguiente, se realizó una gran cantidad de trabajo y se desarrollaron teorías para reducir el número de colores a cuatro, hasta que Kenneth Appel y Wolfgang Haken finalmente demostraron el teorema de los cuatro colores en 1976. La prueba se remontaba a las ideas de Heawood y Kempe y ignoraba en gran medida los desarrollos intermedios. La demostración del teorema de los cuatro colores es digna de mención, además de su solución a un problema centenario, por ser la primera demostración importante asistida por computadora.

En 1912, George David Birkhoff introdujo el polinomio cromático para estudiar el problema de coloración, que Tutte generalizó al polinomio de Tutte, los cuales son invariantes importantes en la teoría de grafos algebraicos. Kempe ya había llamado la atención sobre el caso general no plano en 1879, y a principios del siglo XX siguieron muchos resultados sobre generalizaciones de la coloración de gráficos planos a superficies de orden superior.

En 1960, Claude Berge formuló otra conjetura sobre la coloración de gráficos, la conjetura fuerte del gráfico perfecto, originalmente motivada por un concepto teórico de la información llamado capacidad de error cero de un gráfico introducido por Shannon. La conjetura permaneció sin resolver durante 40 años, hasta que Chudnovsky, Robertson, Seymour y Thomas la establecieron como el célebre teorema del grafo perfecto fuerte en 2002.

La coloración de gráficos se ha estudiado como un problema algorítmico desde principios de la década de 1970: el problema de números cromáticos (ver más abajo) es uno de los 21 problemas NP completos de Karp de 1972, y aproximadamente al mismo tiempo varios problemas exponenciales. Se desarrollaron algoritmos de tiempo basados en el retroceso y en la recurrencia de deleción-contracción de Zykov (1949). Una de las principales aplicaciones de la coloración de gráficos, la asignación de registros en los compiladores, se introdujo en 1981.

Definición y terminología

Coloración de vértices

Cuando se utiliza sin ninguna calificación, una coloración de un gráfico casi siempre se refiere a una coloración de vértice adecuada, es decir, un etiquetado de los vértices del gráfico con colores. de modo que no haya dos vértices que compartan el mismo borde y tengan el mismo color. Dado que un vértice con un bucle (es decir, una conexión directa consigo mismo) nunca podría colorearse adecuadamente, se entiende que los gráficos en este contexto no tienen bucles.

La terminología del uso de colores para etiquetas de vértices se remonta a la coloración del mapa. Etiquetas como rojo y azul sólo se utilizan cuando el número de colores es pequeño, y normalmente se entiende que las etiquetas se extraen de los números enteros {1, 2, 3,…}.

Una coloración que utiliza como máximo k colores se denomina k-coloring. El menor número de colores necesarios para colorear un gráfico G se llama número cromático y, a menudo, se llama denotado χ(G). A veces se utiliza γ(G), ya que χ(G) también se utiliza para indicar la característica de Euler de un gráfico. Un gráfico al que se le puede asignar un color (adecuado) k es k-colorable, y es k-cromático si su número cromático es exactamente k. Un subconjunto de vértices asignados al mismo color se denomina clase de color y cada una de estas clases forma un conjunto independiente. Por lo tanto, una coloración k es lo mismo que una partición del vértice establecido en k conjuntos independientes y los términos k-partite y k-colorable tienen el mismo significado.

Polinomio cromático

El polinomio cromático cuenta el número de formas en que se puede colorear un gráfico utilizando algunos de un número determinado de colores. Por ejemplo, usando tres colores, el gráfico de la imagen adyacente se puede colorear de 12 maneras. Con sólo dos colores, no se puede colorear en absoluto. Con cuatro colores, se puede colorear de 24 + 4⋅12 = 72 maneras: usando los cuatro colores, ¡hay 4! = 24 coloraciones válidas (cada asignación de cuatro colores a cualquier gráfico de 4 vértices es una coloración adecuada); y por cada elección de tres de los cuatro colores, hay 12 3 colores válidos. Entonces, para el gráfico del ejemplo, una tabla del número de colorantes válidos comenzaría así:

El polinomio cromático es una función P(G,t) que cuenta el número de tcoloraciones de G . Como su nombre lo indica, para un G dado, la función es de hecho un polinomio en t. Para el gráfico de ejemplo, P(G,t) = t(t – 1)²(t – 2), y de hecho P (G,4) = 72.

El polinomio cromático incluye más información sobre la colorabilidad de G que el número cromático. De hecho, χ es el entero positivo más pequeño que no es un cero del polinomio cromático χ(G) = min{k: P(G,k) > 0}.

Coloración de bordes

Una coloración de bordes de un gráfico es una coloración adecuada de los bordes, es decir, una asignación de colores a los bordes de modo que ningún vértice incide sobre dos bordes del mismo color. Una coloración de borde con colores k se denomina k-edge-coloring y es equivalente al problema de dividir el conjunto de bordes en k coincidencias. El menor número de colores necesarios para colorear los bordes de un gráfico G es el índice cromático, o número cromático de borde, χ′(G). Una coloración Tait es una coloración de 3 aristas de un gráfico cúbico. El teorema de los cuatro colores equivale a la afirmación de que todo grafo cúbico plano sin puente admite una coloración Tait.

Coloración total

coloración total es un tipo de coloración en los vértices y de un gráfico. Cuando se utiliza sin ninguna calificación, siempre se supone que una coloración total es adecuada en el sentido de que a ningún vértice adyacente, ni aristas adyacentes, ni a ninguna arista y sus vértices finales se les asigna el mismo color. El número cromático total χ″(G) de un gráfico G es la menor cantidad de colores necesarios en cualquier coloración total de G.

Coloración sin etiqueta

Una coloración sin etiqueta de un gráfico es una órbita de una coloración bajo la acción del grupo de automorfismos del gráfico. Los colores permanecen etiquetados; es el gráfico el que no está etiquetado. Existe un análogo del polinomio cromático que cuenta el número de coloraciones sin etiquetar de un gráfico de un conjunto finito de colores determinado.

Si interpretamos una coloración de un gráfico en d vertices como vector en Zd{displaystyle mathbb {Z} {d}, la acción de un automorfismo es una permutación de los coeficientes en el vector de color.

Propiedades

Límites superiores del número cromático

Asignar colores distintos a vértices distintos siempre produce una coloración adecuada, por lo que

1≤ ≤ χ χ ()G)≤ ≤ n.{displaystyle 1leq chi (G)leq n.}

Los únicos gráficos que pueden ser de 1 color son gráficos sin borde. Un gráfico completo Kn{displaystyle K_{n} de n vertices requiere χ χ ()Kn)=n{displaystyle chi (K_{n}=n} colores. En un color óptimo debe haber al menos uno de los gráficos m bordes entre cada par de clases de color, así que

χ χ ()G)()χ χ ()G)− − 1)≤ ≤ 2m.{displaystyle chi (G)(chi (G)-1)leq 2m.}

Más generalmente una familia F{displaystyle {fnMithcal}} de gráficos es χ χ {displaystyle chi }- Abundado si hay alguna función c{displaystyle c} tal que los gráficos G{displaystyle G. dentro F{displaystyle {fnMithcal}} se puede colorear con c()⋅ ⋅ ()G)){displaystyle c(omega (G)} colores, para la familia de los gráficos perfectos esta función es c()⋅ ⋅ ()G))=⋅ ⋅ ()G){displaystyle c(omega (G)=omega (G)}.

Los gráficos de 2 colores son exactamente gráficos bipartitos, incluidos árboles y bosques. Según el teorema de los cuatro colores, todo gráfico plano puede tener 4 colores.

Una coloración codiciosa muestra que cada gráfico se puede colorear con un color más que el grado máximo de vértice,

χ χ ()G)≤ ≤ Δ Δ ()G)+1.{displaystyle chi (G)leq Delta (G)+1.}

Los gráficos completos tienen χ χ ()G)=n{displaystyle chi (G)=n} y Δ Δ ()G)=n− − 1{displaystyle Delta (G)=n-1}, y los ciclos extraños tienen χ χ ()G)=3{displaystyle chi (G)=3} y Δ Δ ()G)=2{displaystyle Delta (G)=2}, así que para estos gráficos este límite es mejor posible. En todos los demás casos, el límite puede mejorarse ligeramente; el teorema de Brooks afirma que

Teorema de Brooks: χ χ ()G)≤ ≤ Δ Δ ()G){displaystyle chi (G)leq Delta (G)} para un gráfico conectado, simple G, a menos que G es un gráfico completo o un ciclo extraño.

Límites inferiores del número cromático

A lo largo de los años se han descubierto varios límites inferiores para los límites cromáticos:

Si G contiene un grupo de tamaño k, entonces se necesitan al menos k colores para colorear ese grupo; en otras palabras, el número cromático es al menos el número de camarilla:

χ χ ()G)≥ ≥ ⋅ ⋅ ()G).{displaystyle chi (G)geq omega (G).}

Para gráficos perfectos, este límite es ajustado. Encontrar camarillas se conoce como el problema de las camarillas.

Hoffman está obligado: Vamos W{displaystyle W. ser una matriz simétrica real tal que Wi,j=0{displaystyle W_{i,j}=0} siempre ()i,j){displaystyle (i,j)} no es un borde en G{displaystyle G.. Define χ χ W()G)=1− − λ λ max()W)λ λ min()W){displaystyle chi ¿Por qué?, donde λ λ max()W),λ λ min()W){displaystyle lambda _{max }(W),lambda _{min }(W)} son los eigenvalues más grandes y pequeños de W{displaystyle W.. Define χ χ H()G)=maxWχ χ W()G){textstyle chi _{H}(G)=max _{W}chi _{W}(G)}, con W{displaystyle W. como arriba. Entonces:

χ χ H()G)≤ ≤ χ χ ()G).{displaystyle chi _{H}(G)leq chi (G).}

Número cromático Vector: Vamos W{displaystyle W. ser una matriz semi-definida positiva tal que Wi,j≤ ≤ − − 1k− − 1{displaystyle W_{i,j}leq -{tfrac {1}{k-1}} siempre ()i,j){displaystyle (i,j)} es un borde en G{displaystyle G.. Define χ χ V()G){displaystyle chi _{V}(G)} para ser el mínimo k para el cual tal matriz W{displaystyle W. existe. Entonces...

χ χ V()G)≤ ≤ χ χ ()G).{displaystyle chi _{V}(G)leq chi (G).}

Número de Lovász: El número de Lovász de un gráfico complementario es también un límite inferior del número cromático:

Silencio Silencio ()Ḡ ̄ )≤ ≤ χ χ ()G).{displaystyle vartheta ({bar {G})leq chi (G).}

Número cromático fraccionario: El número cromático fraccionario de una gráfica también es un límite inferior del número cromático:

χ χ f()G)≤ ≤ χ χ ()G).{displaystyle chi _{f}(G)leq chi (G).}

Estos límites están ordenados de la siguiente manera:

χ χ H()G)≤ ≤ χ χ V()G)≤ ≤ Silencio Silencio ()Ḡ ̄ )≤ ≤ χ χ f()G)≤ ≤ χ χ ()G).{displaystyle chi _{H}(G)leq chi _{V}(G)leq vartheta ({bar {G}})leq chi _{f}(G)leq chi (G). }

Gráficos con alto número cromático

Los gráficos con camarillas grandes tienen un número cromático elevado, pero no ocurre lo contrario. El gráfico de Grötzsch es un ejemplo de un gráfico de 4 cromáticos sin triángulo, y el ejemplo se puede generalizar a los mycielskianos.

Theorem (William T. Tutte 1947, Alexander Zykov 1949, Jan Mycielski 1955): Existen gráficos sin triángulo con un número cromático arbitrariamente alto.

Para probar esto, tanto Mycielski como Zykov, cada uno dio una construcción de una familia inductivamente definida de gráficos sin triángulo pero con un número cromático arbitrariamente grande. Burling (1965) construido cajas alineadas de eje en R3{displaystyle mathbb {R} {} {}}} cuyo gráfico de intersección es libre de triángulo y requiere arbitrariamente muchos colores para ser correctamente coloreado. Esta familia de gráficos se llama entonces los gráficos Burling. La misma clase de gráficos se utiliza para la construcción de una familia de segmentos sin triángulo en el plano, dado por Pawlik et al. (2014). Muestra que el número cromático de su gráfico de intersección es arbitrariamente grande también. Por lo tanto, esto implica que las cajas alineadas del eje en R3{displaystyle mathbb {R} {} {}}} así como segmentos de línea en R2{displaystyle mathbb {R} {2}} no tienen χ.

Según el teorema de Brooks, las gráficas con un número cromático alto deben tener un grado máximo alto. Pero la colorabilidad no es un fenómeno enteramente local: un gráfico con gran circunferencia se parece localmente a un árbol, porque todos los ciclos son largos, pero su número cromático no tiene por qué ser 2:

Theorem (Erdős): Existen gráficas de circunferencia arbitrariamente alta y número cromático.

Límites del índice cromático

Un borde para colorear G es un vértice para colorear su gráfico de línea L()G){displaystyle L(G)}, y viceversa. Así,

χ χ .()G)=χ χ ()L()G)).{displaystyle chi '(G)=chi (L(G)). }

Hay una fuerte relación entre la colorabilidad del borde y el grado máximo del gráfico Δ Δ ()G){displaystyle Delta (G)}. Puesto que todos los bordes incidente al mismo vértice necesitan su propio color, tenemos

χ χ .()G)≥ ≥ Δ Δ ()G).{displaystyle chi '(G)geq Delta (G). }

Además,

Teorema de Kőnig: χ χ .()G)=Δ Δ ()G){displaystyle chi '(G)=Delta (G)} si G es bipartito.

In general, the relationship is even stronger than what Brooks 's theorem gives for vertex coloring:

El teorema de Vizing: Gráfico de grado máximo Δ Δ {displaystyle Delta } tiene número de borde-cromático Δ Δ {displaystyle Delta } o Δ Δ +1{displaystyle Delta +1}.

Otras propiedades

Un gráfico tiene una coloración k si y sólo si tiene una orientación acíclica para la cual el camino más largo tiene una longitud como máximo k; este es el teorema de Gallai-Hasse-Roy-Vitaver (Nešetřil & Ossona de Mendez 2012).

Para los gráficos planos, las coloraciones de los vértices son esencialmente flujos duales a cero en ninguna parte.

Acerca de los gráficos infinitos, se sabe mucho menos. Los siguientes son dos de los pocos resultados sobre la coloración de gráficos infinitos:

• Si todos los subgrafos finitos de un gráfico infinito G son k-colorable, entonces lo es G, bajo la suposición del axioma de elección. Este es el teorema de Bruijn-Erdős de Bruijn ' Erdős (1951).
• Si un gráfico admite todo n-colorante para cada n ≥ n₀, admite una coloración completa infinita (Fawcett 1978).

Problemas abiertos

Como se ha indicado anteriormente, ⋅ ⋅ ()G)≤ ≤ χ χ ()G)≤ ≤ Δ Δ ()G)+1.{displaystyle omega (G)leq chi (G)leq Delta (G)+1.} Una conjetura de Reed desde 1998 es que el valor está esencialmente más cerca del límite inferior, χ χ ()G)≤ ≤ ⌈⋅ ⋅ ()G)+Δ Δ ()G)+12⌉.{displaystyle chi (G)leq leftlceil {frac {omega (G)+ Delta.

El número cromático del plano, donde dos puntos son adyacentes si tienen una unidad de distancia, se desconoce, aunque es uno de 5, 6 o 7. Otros problemas abiertos relacionados con el número cromático de gráficos incluyen la conjetura de Hadwiger que establece que cada gráfico con número cromático k tiene un gráfico completo en k vértices como menor, la conjetura de Erdős-Faber-Lovász que limita el número cromático de uniones de gráficos completos que tienen como máximo un vértice en común para cada par, y la conjetura de Albertson de que entre los grafos k-cromáticos los grafos completos son los que tienen menor número de cruces.

Cuando Birkhoff y Lewis introdujeron el polinomio cromático en su ataque contra el teorema de cuatro colores, conjeturaron que para gráficos plano G, el polinomio P()G,t){displaystyle P(G,t)} no tiene ceros en la región [4,JUEGO JUEGO ){displaystyle [4,infty]}. Aunque se sabe que tal polinomio cromático no tiene ceros en la región [5,JUEGO JUEGO ){displaystyle [5,infty]} y eso P()G,4)ل ل 0{displaystyle P(G,4)neq 0}, su conjetura sigue sin resolverse. También sigue siendo un problema sin resolver para caracterizar los gráficos que tienen el mismo polinomio cromático y para determinar qué polinomios son cromáticos.

Algoritmos

Tiempo polinómico

Determinar si un gráfico se puede colorear con 2 colores equivale a determinar si el gráfico es bipartito o no y, por lo tanto, computable en tiempo lineal mediante búsqueda en amplitud o búsqueda en profundidad. De manera más general, el número cromático y la coloración correspondiente de gráficos perfectos se pueden calcular en tiempo polinómico mediante programación semidefinida. Se conocen fórmulas cerradas para polinomios cromáticos para muchas clases de gráficos, como bosques, gráficos cordales, ciclos, ruedas y escaleras, por lo que pueden evaluarse en tiempo polinómico.

Si el gráfico es plano y tiene un ancho de rama bajo (o no es plano pero con una descomposición de rama conocida), entonces se puede resolver en tiempo polinómico usando programación dinámica. En general, el tiempo requerido es polinómico en el tamaño del gráfico, pero exponencial en el ancho de la rama.

Algoritmos exactos

Búsqueda de fuerza bruta para un k-colorante considera cada uno de los kn{displaystyle k^{n} asignaciones de k colores a n vertices y cheques para cada uno si es legal. Para calcular el número cromático y el polinomio cromático, este procedimiento se utiliza para cada k=1,...... ,n− − 1{displaystyle k=1,ldotsn-1}, poco práctico para todos pero los gráficos de entrada más pequeños.

Utilizando la programación dinámica y un vínculo con el número de conjuntos máximos independientes, k-colorabilidad se puede decidir en el tiempo y el espacio O()2.4423n){displaystyle O(2.4423^{n}}. Usando el principio de inclusión –exclusión y algoritmo de Yates para la rápida transformación de zeta, k-colorabilidad se puede decidir a tiempo O()2nn){displaystyle O(2^{n}n)} para cualquier k. Los algoritmos más rápidos son conocidos por 3- y 4-colorabilidad, que se puede decidir en el tiempo O()1.3289n){displaystyle O(1.3289^{n}} y O()1.7272n){displaystyle O(1.7272^{n}}, respectivamente. Los algoritmos exponencialmente más rápidos también son conocidos por 5- y 6-colorabilidad, así como para familias restringidas de gráficos, incluyendo gráficos escasos.

Construction

La contracción G/uv{displaystyle G/uv} de un gráfico G es el gráfico obtenido identificando los vértices u y v, y quitar cualquier borde entre ellos. Los bordes restantes se produjeron originalmente a u o v son ahora incidentes a su identificación (i.e., el nuevo nodo fusionado uv). Esta operación desempeña un papel importante en el análisis de la coloración de gráficos.

El número cromático satisface la relación de recurrencia:

χ χ ()G)=min{}χ χ ()G+uv),χ χ ()G/uv)}{displaystyle chi (G)={min}{chi (G+uv),chi (G/uv)}}

por Zykov (1949), donde u y v son vértices no adyacentes, y G+uv{displaystyle G+uv} es el gráfico con el borde uv añadido. Varios algoritmos se basan en evaluar esta recurrencia y el árbol resultante de la computación se llama a veces un árbol Zykov. El tiempo de funcionamiento se basa en una heurística para elegir los vértices u y v.

El polinomio cromático satisface la siguiente relación de recurrencia

P()G− − uv,k)=P()G/uv,k)+P()G,k){displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}

Donde u y v son vértices adyacentes, y G− − uv{displaystyle G-uv} es el gráfico con el borde uv Retirada. P()G− − uv,k){displaystyle P(G-uv,k)} representa el número de posibles colores adecuados del gráfico, donde los vértices pueden tener los mismos o diferentes colores. Entonces los colores adecuados surgen de dos gráficos diferentes. Para explicar, si los vértices u y v tienen diferentes colores, entonces podríamos considerar un gráfico donde u y v están adyacentes. Si u y v tenemos los mismos colores, podemos considerar un gráfico donde u y v son contratados. La curiosidad de Tutte sobre qué otras propiedades gráficas satisfizo esta recurrencia le llevó a descubrir una generalización bivariada del polinomio cromático, el polinomio Tutte.

Estas expresiones dan lugar a un procedimiento recursivo llamado el deleción– algoritmo de tracción, que forma la base de muchos algoritmos para colorear gráfico. El tiempo de funcionamiento satisface la misma relación de recurrencia que los números Fibonacci, por lo que en el peor de los casos el algoritmo se ejecuta en el tiempo dentro de un factor polinomio ()1+52)n+m=O()1.6180n+m){displaystyle left({tfrac {1+{sqrt {5}}{2}derecha)} {n+m}=O(1.6180^{n+m}} para n vértices y m bordes. El análisis puede mejorarse dentro de un factor polinomio del número t()G){displaystyle t(G)} de árboles azotados del gráfico de entrada. En la práctica, las estrategias ramificadas y ligadas y el rechazo del isomorfismo gráfico se emplean para evitar algunas llamadas recursivas. El tiempo de funcionamiento depende de la heurística utilizada para elegir el par de vértice.

Colorante codiciosa

El algoritmo codicioso considera los vértices en un orden específico v1{displaystyle v_{1},...vn{displaystyle V_{n} y cede a vi{displaystyle V_{i} el color más pequeño disponible no utilizado por vi{displaystyle V_{i}'s vecinos entre v1{displaystyle v_{1},...vi− − 1{displaystyle v_{i-1}, añadiendo un color fresco si es necesario. La calidad de la coloración resultante depende del pedido elegido. Existe un pedido que conduce a una coloración codictiva con el número óptimo de χ χ ()G){displaystyle chi (G)} colores. Por otro lado, los colorantes codiciosos pueden ser arbitrariamente malos; por ejemplo, el gráfico de la corona en n vertices pueden ser de 2 colores, pero tiene un orden que conduce a una coloración codicioso con n/2{displaystyle n/2} colores.

Para gráficos cordales, y para casos especiales de gráficos cordales, como gráficos de intervalos y gráficos de indiferencia, el algoritmo de coloración codiciosa se puede utilizar para encontrar coloraciones óptimas en tiempo polinómico, eligiendo el orden de los vértices como el inverso de una eliminación perfecta. ordenar el gráfico. Las gráficas perfectamente ordenables generalizan esta propiedad, pero es NP-difícil encontrar un orden perfecto de estas gráficas.

Si los vértices se ordenan según sus grados, el colorante avaro resultante utiliza a la mayoría maximin{}d()xi)+1,i}{displaystyle {text{max}_{i}{text{i} {f}} {f}}} {f}}} {f}f}}f}} {f}}}}} {fnf}}}}}} {f}f}f}}}}}}}\f}f}f}}}}}}}}}}\\f}f}f}f}f}f}f}f}f} {f}f}f}f}f} {b9}}}}}}}}}}}}\\\f}f}}}}f}}}}}f}}}}}}f}}\\\\\f}}}}}}}}}}}}}}}f}}}}}}}}\\\\\f}}}}}} ## min}{d(x_{i})+1,i} colores, en la mayoría de uno más que el grado máximo del gráfico. Esta heurística a veces se llama el algoritmo Welsh-Powell. Otro heurista debido a Brélaz establece la orden dinámicamente mientras el algoritmo avanza, eligiendo el vértice adyacente al mayor número de colores diferentes. Muchos otros heurísticos de color gráfico se basan igualmente en la coloración codicioso para una estrategia estática o dinámica específica de ordenar los vértices, estos algoritmos a veces se llaman coloración secuencial algoritmos.

El número máximo (peor) de colores que se puede obtener mediante el algoritmo codicioso, utilizando un orden de vértices elegido para maximizar este número, se llama número de Grundy de un gráfico.

Algoritmos heurísticos

Dos heurísticas de tiempo polinómico bien conocidas para colorear gráficos son el algoritmo DSatur y el algoritmo recursivo más grande primero (RLF).

De manera similar al algoritmo de coloración codiciosa, DSatur colorea los vértices de un gráfico uno tras otro, gastando un color no utilizado previamente cuando es necesario. Una vez que se ha coloreado un nuevo vértice, el algoritmo determina cuál de los vértices restantes sin colorear tiene el mayor número de colores diferentes en su vecindad y colorea este vértice a continuación. Esto se define como el grado de saturación de un vértice determinado.

El primer algoritmo recursivo más grande opera de una manera diferente al construir cada clase de color una a la vez. Para ello, identifica un conjunto máximo independiente de vértices en el gráfico utilizando reglas heurísticas especializadas. Luego asigna estos vértices al mismo color y los elimina del gráfico. Estas acciones se repiten en el subgrafo restante hasta que no queden vértices.

La peor complejidad de DSatur es O()n2){displaystyle O(n^{2}}, donde n{displaystyle n} es el número de vértices en el gráfico. El algoritmo también se puede implementar utilizando un montón binario para almacenar grados de saturación, operando en O()()n+m)log⁡ ⁡ n){displaystyle O(n+m)log n)} Donde m{displaystyle m} es el número de bordes en el gráfico. Esto produce carreras mucho más rápidas con gráficos escasos. La complejidad general de RLF es ligeramente superior a DSatur en O()mn){displaystyle {mathcal}(mn)}.

DSatur y RLF son exactos para gráficos bipartitos, de ciclo y de rueda.

Algoritmos paralelos y distribuidos

En el campo de los algoritmos distribuidos, la coloración de gráficos está estrechamente relacionada con el problema de la ruptura de simetría. Los algoritmos aleatorios de última generación son más rápidos para un grado máximo Δ suficientemente grande que los algoritmos deterministas. Los algoritmos aleatorios más rápidos emplean la técnica de ensayos múltiples de Schneider et al.

En un gráfico simétrico, un algoritmo distribuido determinista no puede encontrar una coloración de vértice adecuada. Se necesita alguna información auxiliar para romper la simetría. Una suposición estándar es que inicialmente cada nodo tiene un identificador único, por ejemplo, del conjunto {1, 2,..., n}. Dicho de otra manera, asumimos que se nos da una coloración n. El desafío es reducir el número de colores de n a, por ejemplo, Δ + 1. Cuantos más colores se empleen, por ejemplo, O(Δ) en lugar de Δ + 1, menos rondas de comunicación se requieren.

Una versión distribuida sencilla del algoritmo codicioso para la coloración (Δ + 1) requiere Θ(n) rondas de comunicación en el peor de los casos: es posible que sea necesario propagar la información desde un lado de la red. a otro lado.

El caso interesante más simple es un ciclo n. Richard Cole y Uzi Vishkin muestran que existe un algoritmo distribuido que reduce el número de colores de n a O(log n) en una secuencia sincrónica. paso de comunicación. Al repetir el mismo procedimiento, es posible obtener una coloración triple de un ciclo n en O(log* n) pasos de comunicación. (suponiendo que tengamos identificadores de nodo únicos).

La función log*, logaritmo iterado, es una función de crecimiento extremadamente lento, "casi constante". Por lo tanto, el resultado de Cole y Vishkin planteó la cuestión de si existe un algoritmo distribuido en tiempo constante para colorear con 3 colores un ciclo n. Linial (1992) demostró que esto no es posible: cualquier algoritmo distribuido determinista requiere Ω(log* n) pasos de comunicación para reducir una coloración n a una coloración de 3. un ciclo n.

La técnica de Cole y Vishkin se puede aplicar también en gráficos arbitrarios de grado consolidado; el tiempo de funcionamiento es poli(Δ) + O(log*n). La técnica se extendió a gráficos de disco unitario por Schneider et al. Los algoritmos deterministas más rápidos para (Δ + 1)-coloring para pequeño Δ se deben a Leonid Barenboim, Michael Elkin y Fabian Kuhn. El algoritmo de Barenboim et al. se ejecuta en el tiempo O(Δ) + log*(n)/2, que es óptimo en términos de n ya que el factor constante 1/2 no se puede mejorar debido al límite inferior de Linial. Panconesi & Srinivasan (1996) utilizan descomposiciones de red para calcular un colorante Δ+1 en el tiempo 2O()log⁡ ⁡ n){displaystyle 2^{Oleft({sqrt {log n}right)}}.

El problema de la coloración de los bordes también se ha estudiado en el modelo distribuido. Panconesi & Rizzi (2001) logra una coloración (2Δ − 1) en tiempo O(Δ + log* n) en este modelo. El límite inferior para la coloración distribuida de vértices debido a Linial (1992) se aplica también al problema de coloración distribuida de bordes.

Algoritmos descentralizados

Los algoritmos descentralizados son aquellos en los que no se permite el paso de mensajes (a diferencia de los algoritmos distribuidos donde se realiza el paso de mensajes local), y existen algoritmos descentralizados eficientes que colorearán un gráfico si existe una coloración adecuada. Estos suponen que un vértice es capaz de detectar si alguno de sus vecinos está usando el mismo color que el vértice, es decir, si existe un conflicto local. Esta es una suposición leve en muchas aplicaciones, p. En la asignación de canales inalámbricos suele ser razonable suponer que una estación podrá detectar si otros transmisores que interfieren están utilizando el mismo canal (por ejemplo, midiendo la SINR). Esta información de detección es suficiente para permitir que los algoritmos basados en autómatas de aprendizaje encuentren un color de gráfico adecuado con probabilidad uno.

Complejidad computacional

La coloración de gráficos es difícil desde el punto de vista computacional. Es NP-completo decidir si un gráfico dado admite una coloración k para un k dado, excepto en los casos k ∈ {0, 1,2}. En particular, es NP-difícil calcular el número cromático. El problema de los 3 colores sigue siendo NP completo incluso en gráficos planos de 4 regulares. Sin embargo, en gráficos con grado máximo 3 o menos, Brooks' El teorema implica que el problema de los 3 colores se puede resolver en tiempo lineal. Además, por cada k > 3, existe una coloración k de un gráfico plano según el teorema de los cuatro colores, y es posible encontrar dicha coloración en tiempo polinomial.

El algoritmo de aproximación más conocido calcula una coloración del tamaño como máximo dentro de un factor O(n(log log n)²(log n)⁻³) del número cromático. Para todos los ε > 0, la aproximación del número cromático dentro de n^1−ε es NP-duro.

También es NP-hard para colorear un gráfico de 3 colores con 5 colores, un gráfico de 4 colores con 7 colores y un k- gráfico colorable con ()k⌊ ⌊ k/2⌋ ⌋ )− − 1{displaystyle textstyle {binom}{lfloor k/2rfloor ♪♪ colores para k ≥ 5.

Computing the coefficients of the chromatic polynomial is #P-hard. De hecho, incluso computar el valor χ χ ()G,k){displaystyle chi (G,k)} es #P-hard en cualquier punto racional k excepto para k= 1 y k= 2. No hay FPRAS para evaluar el polinomio cromático en cualquier punto racional k≥ 1,5 excepto k= 2 a menos que NP = RP.

Para colorear bordes, la prueba del resultado de Vizing proporciona un algoritmo que utiliza como máximo Δ+1 colores. Sin embargo, decidir entre los dos valores candidatos para el número cromático del borde es NP-completo. En términos de algoritmos de aproximación, el algoritmo de Vizing muestra que el número cromático del borde se puede aproximar dentro de 4/3, y el resultado de dureza muestra que no existe ningún algoritmo (4/3 − ε) para ningún ε > 0 a menos que P = NP. Estos se encuentran entre los resultados más antiguos en la literatura sobre algoritmos de aproximación, aunque ninguno de los artículos hace uso explícito de esa noción.

Aplicaciones

Programación

Modelos de coloración de vértices para una serie de problemas de programación. En la forma más clara, un conjunto determinado de trabajos debe asignarse a franjas horarias; cada trabajo requiere una de esas franjas horarias. Los trabajos se pueden programar en cualquier orden, pero los pares de trabajos pueden estar en conflicto en el sentido de que no se pueden asignar al mismo intervalo de tiempo, por ejemplo, porque ambos dependen de un recurso compartido. El gráfico correspondiente contiene un vértice para cada trabajo y una arista para cada par de trabajos en conflicto. El número cromático del gráfico es exactamente el makespan mínimo, el momento óptimo para terminar todos los trabajos sin conflictos.

Los detalles del problema de programación definen la estructura del gráfico. Por ejemplo, al asignar aviones a vuelos, el gráfico de conflicto resultante es un gráfico de intervalo, por lo que el problema de coloración se puede resolver de manera eficiente. En la asignación de ancho de banda a estaciones de radio, el gráfico de conflicto resultante es un gráfico de disco unitario, por lo que el problema de coloración es 3 aproximado.

Asignación de registros

Un compilador es un programa informático que traduce un lenguaje informático a otro. Para mejorar el tiempo de ejecución del código resultante, una de las técnicas de optimización del compilador es la asignación de registros, donde los valores más utilizados del programa compilado se mantienen en los registros rápidos del procesador. Idealmente, los valores se asignan a los registros para que todos puedan residir en los registros cuando se utilicen.

El enfoque de los libros de texto para este problema es modelarlo como un problema de coloración de gráficos. El compilador construye un gráfico de interferencia, donde los vértices son variables y un borde conecta dos vértices si se necesitan al mismo tiempo. Si el gráfico se puede colorear con k colores, entonces cualquier conjunto de variables necesarias al mismo tiempo se puede almacenar como máximo en registros k.

Otras aplicaciones

El problema de colorear un gráfico surge en muchas áreas prácticas, como la combinación de patrones, la programación de deportes, el diseño de planos de asientos, los horarios de exámenes, la programación de taxis y la resolución de sudokus.

Otros colorantes

Teoría de Ramsey

Una clase importante impropio Los problemas de coloración se estudian en la teoría de Ramsey, donde los bordes del gráfico se asignan a los colores, y no hay restricción en los colores de los bordes del incidente. Un ejemplo simple es el teorema de amigos y extraños, que afirma que en cualquier coloración de los bordes de K6{displaystyle K_{6}, el gráfico completo de seis vértices, habrá un triángulo monocromático; a menudo ilustrado diciendo que cualquier grupo de seis personas tiene tres extraños mutuos o tres conocidos mutuos. La teoría de Ramsey está preocupada por las generalizaciones de esta idea para buscar la regularidad en medio del desorden, encontrando condiciones generales para la existencia de subgrafos monocromáticos con estructura dada.

Otros colorantes

También se puede considerar la coloración para gráficos con signos y gráficos de ganancia.