En el estudio de problemas de coloración de gráficos en matemáticas e informática , una coloración codiciosa o coloración secuencial [1] es una coloración de los vértices de un gráfico formada por un algoritmo codicioso que considera los vértices del gráfico en secuencia y asigna a cada vértice su Primer color disponible. Los colorantes golosos se pueden encontrar en el tiempo lineal, pero, por lo general, no utilizan el mínimo número de colores posible.
Diferentes elecciones de la secuencia de vértices normalmente producirán diferentes coloraciones del gráfico dado, por lo que gran parte del estudio de las coloraciones codiciosas se ha centrado en cómo encontrar un buen orden. Siempre existe un orden que produce una coloración óptima, pero aunque dichos ordenamientos se pueden encontrar para muchas clases especiales de gráficos, en general son difíciles de encontrar. Las estrategias comúnmente utilizadas para ordenar los vértices implican colocar los vértices de mayor grado antes que los de menor grado, o elegir vértices con menos colores disponibles en lugar de vértices que están menos restringidos.
Las variaciones de coloración codiciosa eligen los colores en línea , sin ningún conocimiento de la estructura de la parte no coloreada del gráfico, o eligen otros colores además de los primeros disponibles para reducir el número total de colores. Se han aplicado algoritmos de coloración codiciosa a problemas de programación y asignación de registros , el análisis de juegos combinatorios y las pruebas de otros resultados matemáticos, incluido el teorema de Brooks sobre la relación entre coloración y grado. Otros conceptos en teoría de grafos derivados de coloraciones codiciosas incluyen el número de Grundy de un gráfico (el mayor número de colores que se puede encontrar mediante una coloración codiciosa) y los gráficos bien coloreados , gráficos para los cuales todas las coloraciones codiciosas usan el mismo número de colores.
La coloración codiciosa para un orden de vértice determinado se puede calcular mediante un algoritmo que se ejecuta en tiempo lineal . El algoritmo procesa los vértices en el orden dado, asignando un color a cada uno a medida que se procesa. Los colores pueden representarse mediante números y a cada vértice se le asigna el color con el número más pequeño que no haya sido utilizado por uno de sus vecinos. Para encontrar el color más pequeño disponible, se puede usar una matriz para contar el número de vecinos de cada color (o, alternativamente, para representar el conjunto de colores de los vecinos) y luego escanear la matriz para encontrar el índice de su primer cero. [2]
En Python , el algoritmo se puede expresar como:
def first_available ( color_list ): """Devuelve el entero más pequeño no negativo que no está en la lista de colores dada.""" color_set = set ( color_list ) recuento = 0 mientras que Verdadero : si el recuento no está en color_set : devuelve recuento de recuento += 1 def greedy_color ( G , orden ): """Encuentre el color codicioso de G en el orden dado. Se supone que la representación de G es como https://www.python.org/doc/essays/graphs/ al permitir vecinos de un nodo/vértice que será iterado por "para w en G[nodo]". El valor de retorno es un diccionario que asigna los vértices a sus colores.""" color = dict () para el nodo en orden : used_neighbour_colors = [ color [ nbr ] para nbr en G [ nodo ] si nbr en color ] color [ nodo ] = first_available ( colores_vecinos_usados ) color de retorno La first_availablesubrutina tarda un tiempo proporcional a la longitud de su lista de argumentos, porque realiza dos bucles, uno sobre la lista misma y otro sobre una lista de recuentos que tiene la misma longitud. El tiempo para el algoritmo de coloración general está dominado por las llamadas a esta subrutina. Cada borde del gráfico contribuye solo a una de estas llamadas, la del punto final del borde que se encuentra más adelante en el orden de los vértices. Por lo tanto, la suma de las longitudes de las listas de argumentos first_availabley el tiempo total del algoritmo son proporcionales al número de aristas en el gráfico. [2]
Un algoritmo alternativo, que produce la misma coloración, [3] consiste en elegir los conjuntos de vértices con cada color, un color a la vez. En este método, cada clase de color se elige escaneando los vértices en el orden dado. Cuando este escaneo encuentra un vértice sin color que no tiene ningún vecino en , lo agrega a . De esta manera, se convierte en un conjunto máximo independiente entre los vértices a los que aún no se les asignaron colores más pequeños. El algoritmo encuentra repetidamente clases de color de esta manera hasta que todos los vértices estén coloreados. Sin embargo, implica realizar múltiples escaneos del gráfico, un escaneo para cada clase de color, en lugar del método descrito anteriormente, que utiliza solo un escaneo. [4]
Los diferentes ordenamientos de los vértices de un gráfico pueden hacer que la coloración codiciosa utilice diferentes números de colores, que van desde el número óptimo de colores hasta, en algunos casos, un número de colores que es proporcional al número de vértices del gráfico. Por ejemplo, un gráfico de corona (un gráfico formado a partir de dos conjuntos disjuntos de n /2 vértices { a 1 , a 2 , ... } y { b 1 , b 2 , ... } conectando a i con b j siempre que i ≠ j ) puede ser un caso particularmente malo para la coloración codiciosa. Con el vértice ordenando a 1 , b 1 , a 2 , b 2 , ... , una coloración codiciosa utilizará n /2 colores, un color para cada par ( a i , b i ) . Sin embargo, el número óptimo de colores para este gráfico es dos, un color para los vértices a i y otro para los vértices b i . [5] También existen gráficos en los que, con alta probabilidad, un orden de vértices elegido aleatoriamente conduce a un número de colores mucho mayor que el mínimo. [6] Por lo tanto, es de cierta importancia en la coloración codiciosa elegir cuidadosamente el orden de los vértices.
Los vértices de cualquier gráfico siempre pueden ordenarse de tal manera que el algoritmo codicioso produzca una coloración óptima. Porque, dada cualquier coloración óptima, se pueden ordenar los vértices por sus colores. Luego, cuando se utiliza un algoritmo codicioso con este orden, la coloración resultante es automáticamente óptima. [7] Sin embargo, debido a que la coloración óptima del gráfico es NP-completa , cualquier subproblema que permita resolver este problema rápidamente, incluido encontrar un orden óptimo para la coloración codiciosa, es NP-difícil . [8]
En los gráficos de intervalos y de cuerdas , si los vértices se ordenan en orden inverso al de eliminación perfecta , entonces los vecinos anteriores de cada vértice formarán una camarilla . Esta propiedad hace que la coloración codiciosa produzca una coloración óptima, porque nunca usa más colores de los necesarios para cada una de estas camarillas. Un orden de eliminación se puede encontrar en el tiempo lineal, cuando existe. [9]
Más claramente, cualquier orden de eliminación perfecto es hereditariamente óptimo , lo que significa que es óptimo tanto para el gráfico en sí como para todos sus subgrafos inducidos . Las gráficas perfectamente ordenables (que incluyen gráficas cordales , gráficas de comparabilidad y gráficas hereditarias de distancia ) se definen como gráficas que tienen un ordenamiento hereditariamente óptimo. [10] Reconocer gráficos perfectamente ordenables también es NP-completo. [11]
El número de colores producidos por la coloración codiciosa para el peor orden de un gráfico dado se llama número de Grundy . [12] Así como encontrar un buen orden de vértices para una coloración codiciosa es difícil, también lo es encontrar un mal orden de vértices. Es NP-completo determinar, para un gráfico dado G y un número k , si existe un ordenamiento de los vértices de G que haga que el algoritmo codicioso utilice k o más colores. En particular, esto significa que es difícil encontrar el peor orden para G. [12]
Los gráficos bien coloreados son aquellos en los que todos los ordenamientos de los vértices producen el mismo número de colores. Este número de colores, en estos gráficos, es igual tanto al número cromático como al número de Grundy. [12] Incluyen los cografos , que son exactamente los gráficos en los que todos los subgrafos inducidos están bien coloreados. [13] Sin embargo, es co-NP-completo determinar si un gráfico está bien coloreado. [12]
Si se extrae un gráfico aleatorio del modelo Erdős-Rényi con probabilidad constante de incluir cada borde, entonces cualquier orden de vértice que se elija independientemente de los bordes del gráfico conduce a una coloración cuyo número de colores es cercano al doble del valor óptimo, con alta probabilidad . Aún se desconoce si existe algún método de tiempo polinomial para encontrar coloraciones significativamente mejores de estos gráficos. [3]
Debido a que el ordenamiento óptimo de los vértices es difícil de encontrar, se han utilizado heurísticas que intentan reducir la cantidad de colores sin garantizar una cantidad óptima de colores. Un orden comúnmente utilizado para la coloración codiciosa es elegir un vértice v de grado mínimo , ordenar el subgrafo con v eliminado de forma recursiva y luego colocar v al final del orden. El mayor grado de un vértice eliminado que encuentra este algoritmo se llama degeneración del gráfico, denotado como d . En el contexto de la coloración codiciosa, la misma estrategia de pedido también se denomina último pedido más pequeño. [14] Este orden de vértices y la degeneración se pueden calcular en tiempo lineal. [15] Puede verse como una versión mejorada de un método de ordenación de vértices anterior, el orden más grande primero, que ordena los vértices en orden descendente por sus grados. [dieciséis]
Con el orden de degeneración, la coloración codiciosa utilizará como máximo d + 1 colores. Esto se debe a que, cuando se colorea, cada vértice tendrá como máximo d vecinos ya coloreados, por lo que uno de los primeros d + 1 colores quedará libre para su uso. [17] La coloración codiciosa con el orden de degeneración puede encontrar coloraciones óptimas para ciertas clases de gráficos, incluidos árboles, pseudobosques y gráficos de copas. [18] Markossian, Gasparian y Reed (1996) definen un gráfico como perfecto si, para y cada subgrafo inducido de , el número cromático es igual a la degeneración más uno. Para estos gráficos, el algoritmo codicioso con orden de degeneración siempre es óptimo. [19] Cada gráfico perfecto debe ser un gráfico par sin agujeros , porque los ciclos pares tienen número cromático dos y degeneración dos, no coincidiendo con la igualdad en la definición de gráficos perfectos. Si una gráfica y su gráfica complementaria no tienen agujeros pares, ambas son perfectas. Las gráficas que son tanto gráficas perfectas como gráficas perfectas son exactamente las gráficas cordales . En términos más generales, en gráficos sin agujeros pares, el orden de degeneración aproxima la coloración óptima a como máximo el doble del número óptimo de colores; es decir, su relación de aproximación es 2. [20] En gráficos de discos unitarios su relación de aproximación es 3. [21] El prisma triangular es el gráfico más pequeño para el cual uno de sus ordenamientos de degeneración conduce a una coloración no óptima, y el cuadrado El antiprisma es el gráfico más pequeño que no se puede colorear de manera óptima utilizando ninguno de sus ordenamientos de degeneración. [18]
Brélaz (1979) propone una estrategia, llamada DSatur , para el ordenamiento de vértices en coloración codiciosa que intercala la construcción del ordenamiento con el proceso de coloración. En su versión del algoritmo de coloración codiciosa, el siguiente vértice a colorear en cada paso se elige como el que tiene el mayor número de colores distintos en su vecindario . En caso de empates, se elige entre los vértices empatados un vértice de grado máximo en el subgrafo de vértices sin color. Al realizar un seguimiento de los conjuntos de colores vecinos y sus cardinalidades en cada paso, es posible implementar este método en tiempo lineal. [22]
Este método puede encontrar las coloraciones óptimas para gráficos bipartitos , [23] todos los gráficos de cactus , todos los gráficos de ruedas , todos los gráficos en como máximo seis vértices y casi todos los gráficos coloreables. [24] Aunque Lévêque y Maffray (2005) afirmaron originalmente que este método encuentra coloraciones óptimas para los gráficos de Meyniel , más tarde encontraron un contraejemplo a esta afirmación. [25]
Es posible definir variaciones del algoritmo de coloración codiciosa en las que los vértices del gráfico dado se colorean en una secuencia determinada pero en las que el color elegido para cada vértice no es necesariamente el primer color disponible. Estos incluyen métodos en los que el algoritmo desconoce la parte no coloreada del gráfico, o en los que se le da al algoritmo cierta libertad para tomar mejores decisiones de coloración que el algoritmo codicioso básico.
Se han estudiado estrategias alternativas de selección de colores en el marco de algoritmos en línea . En el problema de coloración de gráficos en línea, los vértices de un gráfico se presentan uno a la vez en un orden arbitrario a un algoritmo de coloración; el algoritmo debe elegir un color para cada vértice, basándose únicamente en los colores y las adyacencias entre los vértices ya procesados. En este contexto, se mide la calidad de una estrategia de selección de color por su ratio competitivo , la relación entre el número de colores que utiliza y el número óptimo de colores para el gráfico dado. [26]
Si no se dan restricciones adicionales en el gráfico, la relación competitiva óptima es sólo ligeramente sublineal. [27] Sin embargo, para gráficos de intervalo , es posible una relación competitiva constante, [28] mientras que para gráficos bipartitos y gráficos dispersos se puede lograr una relación logarítmica. De hecho, para gráficos dispersos, la estrategia estándar de coloración voraz de elegir el primer color disponible logra esta relación competitiva, y es posible demostrar un límite inferior coincidente en la relación competitiva de cualquier algoritmo de coloración en línea. [26]
Una coloración parsimoniosa , para un gráfico y un orden de vértices determinados, se ha definido como una coloración producida por un algoritmo codicioso que colorea los vértices en el orden dado y solo introduce un nuevo color cuando todos los colores anteriores son adyacentes al vértice dado. pero puede elegir qué color usar (en lugar de elegir siempre el más pequeño) cuando puede reutilizar un color existente. El número cromático ordenado es el número más pequeño de colores que se pueden obtener para el orden dado de esta manera, y el número ocromático es el número cromático ordenado más grande entre todas las coloraciones de vértices de un gráfico determinado. A pesar de su diferente definición, el número ocromático siempre es igual al número de Grundy. [29]
Debido a que es rápido y en muchos casos puede usar pocos colores, la coloración codiciosa se puede usar en aplicaciones donde se necesita una coloración de gráficos buena pero no óptima. Una de las primeras aplicaciones del algoritmo codicioso fue a problemas como la programación de cursos, en los que se debe asignar una colección de tareas a un conjunto determinado de franjas horarias, evitando que se asignen tareas incompatibles a la misma franja horaria. [4] También se puede utilizar en compiladores para asignación de registros , aplicándolo a un gráfico cuyos vértices representan valores que se asignarán a los registros y cuyas aristas representan conflictos entre dos valores que no se pueden asignar al mismo registro. [30] En muchos casos, estos gráficos de interferencia son gráficos cordales , lo que permite una coloración codiciosa para producir una asignación de registro óptima. [31]
En teoría de juegos combinatoria , para un juego imparcial dado en forma explícita como un gráfico acíclico dirigido cuyos vértices representan posiciones del juego y cuyas aristas representan movimientos válidos de una posición a otra, el algoritmo de coloración codiciosa (que utiliza el orden inverso del gráfico topológico ) calcula el valor nim de cada posición. Estos valores se pueden utilizar para determinar el juego óptimo en cualquier juego individual o en cualquier suma disyuntiva de juegos. [32]
Para un gráfico de grado máximo Δ , cualquier coloración codiciosa utilizará como máximo Δ + 1 colores. El teorema de Brooks establece que, con dos excepciones ( camarillas y ciclos impares ), como máximo se necesitan Δ colores. Una prueba del teorema de Brooks implica encontrar un orden de vértices en el que los dos primeros vértices sean adyacentes al vértice final pero no adyacentes entre sí, y cada vértice distinto del último tenga al menos un vecino posterior. Para un pedido con esta propiedad, el algoritmo de coloración codiciosa utiliza como máximo Δ colores. [33]
