En el estudio de problemas de coloración de grafos en matemáticas y ciencias de la computación , una coloración voraz o coloración secuencial [1] es una coloración de los vértices de un grafo formada por un algoritmo voraz que considera los vértices del grafo en secuencia y asigna a cada vértice su primer color disponible . Las coloraciones voraces se pueden encontrar en tiempo lineal, pero no utilizan, en general, el mínimo número de colores posible.
Las diferentes opciones de la secuencia de vértices normalmente producirán diferentes coloraciones del grafo dado, por lo que gran parte del estudio de coloraciones voraces se ha centrado en cómo encontrar un buen ordenamiento. Siempre existe un ordenamiento que produce una coloración óptima, pero aunque tales ordenamientos se pueden encontrar para muchas clases especiales de grafos, son difíciles de encontrar en general. Las estrategias que se utilizan comúnmente para el ordenamiento de vértices implican colocar los vértices de grado superior antes que los de grado inferior, o elegir vértices con menos colores disponibles en lugar de vértices que están menos restringidos.
Las variaciones de coloración voraz eligen los colores de manera en línea , sin ningún conocimiento de la estructura de la parte no coloreada del gráfico, o eligen otros colores que el primero disponible para reducir el número total de colores. Los algoritmos de coloración voraz se han aplicado a problemas de programación y asignación de registros , al análisis de juegos combinatorios y a las demostraciones de otros resultados matemáticos, incluido el teorema de Brooks sobre la relación entre coloración y grado. Otros conceptos en la teoría de grafos derivados de coloraciones voraces incluyen el número de Grundy de un grafo (el mayor número de colores que se puede encontrar mediante una coloración voraz) y los grafos bien coloreados , grafos para los que todas las coloraciones voraces utilizan el mismo número de colores.
La coloración voraz para un orden de vértices dado 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 esté ya utilizado por uno de sus vecinos. Para encontrar el color más pequeño disponible, se puede utilizar 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 ( colors ): """Devuelve el entero no negativo más pequeño que no está en el conjunto de colores dado. """ color = 0 while color in colors : color += 1 return color def greedy_coloring ( G , order ): """Encuentra la coloración codiciosa 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 que los vecinos de un nodo/vértice sean iterados por "for w in G[node]". El valor de retorno es un diccionario que asigna los vértices a sus colores. """ coloring = dict () for node in order : used_neighbour_colors = { coloring [ nbr ] for nbr in G [ node ] if nbr in coloring } coloring [ node ] = first_available ( used_neighbour_colors ) return coloringLa 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 arista en el gráfico contribuye solo a una de estas llamadas, la del punto final de la arista que está más adelante en el ordenamiento de vértices. Por lo tanto, la suma de las longitudes de las listas de argumentos a first_available, y el tiempo total para el 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 vecino en , se suma a . De esta manera, se convierte en un conjunto independiente máximo entre los vértices a los que 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 único escaneo. [4]
Diferentes ordenaciones de los vértices de un grafo pueden hacer que la coloración voraz 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 en el grafo. Por ejemplo, un grafo de corona (un grafo formado a partir de dos conjuntos disjuntos de n /2 vértices { a 1 , a 2 , ... } y { b 1 , b 2 , ... } conectando a i a b j siempre que i ≠ j ) puede ser un caso particularmente malo para la coloración voraz. Con el orden de vértices a 1 , b 1 , a 2 , b 2 , ... , una coloración voraz utilizará n /2 colores, un color para cada par ( a i , b i ) . Sin embargo, el número óptimo de colores para este grafo 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, en la coloración codiciosa es de cierta importancia elegir cuidadosamente el orden de los vértices.
Los vértices de cualquier grafo siempre pueden ordenarse de tal manera que el algoritmo voraz produzca una coloración óptima. Porque, dada cualquier coloración óptima, uno puede ordenar los vértices por sus colores. Entonces, cuando uno usa un algoritmo voraz con este orden, la coloración resultante es automáticamente óptima. [7] Sin embargo, debido a que la coloración óptima de grafos es NP-completa , cualquier subproblema que permita resolver este problema rápidamente, incluyendo encontrar un ordenamiento óptimo para la coloración voraz, es NP-difícil . [8]
En los grafos de intervalos y grafos cordales , si los vértices están ordenados en el orden inverso de un orden de eliminación perfecto , entonces los vecinos anteriores de cada vértice formarán una camarilla . Esta propiedad hace que la coloración voraz produzca una coloración óptima, porque nunca utiliza más colores de los necesarios para cada una de estas camarillas. Se puede encontrar un orden de eliminación en tiempo lineal, cuando existe. [9]
Más fuertemente, cualquier orden de eliminación perfecta es hereditariamente óptimo , lo que significa que es óptimo tanto para el gráfico en sí como para todos sus subgráficos inducidos . Los gráficos perfectamente ordenables (que incluyen gráficos cordales , gráficos de comparabilidad y gráficos hereditarios de distancia ) se definen como gráficos 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 voraz para el peor ordenamiento de un grafo dado se denomina su número de Grundy . [12] Así como encontrar un buen ordenamiento de vértices para la coloración voraz es difícil, también lo es encontrar un mal ordenamiento de vértices. Es NP-completo determinar, para un grafo dado G y número k , si existe un ordenamiento de los vértices de G que haga que el algoritmo voraz use k o más colores. En particular, esto significa que es difícil encontrar el peor ordenamiento para G . [12]
Los grafos bien coloreados son aquellos en los que todos los ordenamientos de vértices producen el mismo número de colores. Este número de colores, en estos grafos, es igual tanto al número cromático como al número de Grundy. [12] Entre ellos se incluyen los cografos , que son exactamente los grafos en los que todos los subgrafos inducidos están bien coloreados. [13] Sin embargo, es co-NP-completo determinar si un grafo está bien coloreado. [12]
Si se extrae un grafo aleatorio del modelo de Erdős–Rényi con probabilidad constante de incluir cada arista, entonces cualquier orden de vértices que se elija independientemente de las aristas del grafo conduce a una coloración cuyo número de colores es cercano al doble del valor óptimo, con alta probabilidad . Se desconoce si existe algún método de tiempo polinomial para encontrar coloraciones significativamente mejores de estos grafos. [3]
Debido a que es difícil encontrar ordenaciones óptimas de vértices, se han utilizado heurísticas que intentan reducir la cantidad de colores sin garantizar una cantidad óptima de colores. Una ordenación comúnmente utilizada para la coloración voraz es elegir un vértice v de grado mínimo , ordenar el subgrafo con v eliminado de forma recursiva y luego colocar v en último lugar en la ordenación. El grado más grande de un vértice eliminado que encuentra este algoritmo se denomina degeneración del grafo, denotado d . En el contexto de la coloración voraz, la misma estrategia de ordenación también se denomina el último orden más pequeño. [14] Este ordenamiento de vértices, y la degeneración, se pueden calcular en tiempo lineal. [15] Se puede ver como una versión mejorada de un método de ordenamiento de vértices anterior, el ordenamiento de mayor primero, que ordena los vértices en orden descendente por sus grados. [16]
Con el orden de degeneración, la coloración voraz 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 estará libre para que lo use. [17] La coloración voraz con el orden de degeneración puede encontrar coloraciones óptimas para ciertas clases de grafos, incluidos árboles, pseudobosques y grafos de corona. [18] Markossian, Gasparian y Reed (1996) definen un grafo 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 grafos, el algoritmo voraz con el orden de degeneración siempre es óptimo. [19] Todo grafo -perfecto debe ser un grafo sin agujeros pares , porque los ciclos pares tienen número cromático dos y degeneración dos, lo que no coincide con la igualdad en la definición de grafos -perfectos. Si un grafo y su grafo complementario no tienen agujeros pares, ambos son -perfectos. Los grafos que son tanto grafos perfectos como grafos -perfectos son exactamente los grafos cordales . En grafos sin agujeros pares de manera más general, el orden de degeneración se aproxima a la coloración óptima a lo sumo el doble del número óptimo de colores; es decir, su razón de aproximación es 2. [20] En grafos de disco unitario su razón de aproximación es 3. [21] El prisma triangular es el grafo más pequeño para el cual uno de sus órdenes de degeneración conduce a una coloración no óptima, y el antiprisma cuadrado es el grafo más pequeño que no se puede colorear de manera óptima utilizando ninguno de sus órdenes de degeneración. [18]
Brélaz (1979) propone una estrategia, llamada DSatur , para ordenar vértices en coloración voraz que entrelaza la construcción del ordenamiento con el proceso de coloración. En su versión del algoritmo de coloración voraz, el siguiente vértice a colorear en cada paso se elige como el que tiene el mayor número de colores distintos en su vecindad . En caso de empates, se elige un vértice de grado máximo en el subgrafo de vértices no coloreados de entre los vértices empatados. 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 rueda , todos los gráficos con un máximo de 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 voraz en las que los vértices del gráfico dado se colorean en una secuencia dada, pero en las que el color elegido para cada vértice no es necesariamente el primer color disponible. Entre ellas se 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 las que tomaría el algoritmo voraz básico.
Se han estudiado estrategias alternativas de selección de color en el marco de algoritmos en línea . En el problema de coloración de grafos en línea, los vértices de un grafo 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 relación competitiva , la relación entre el número de colores que utiliza y el número óptimo de colores para el grafo dado. [26]
Si no se dan restricciones adicionales en el gráfico, la relación competitiva óptima es solo ligeramente sublineal. [27] Sin embargo, para los gráficos de intervalo , es posible una relación competitiva constante, [28] mientras que para los gráficos bipartitos y los gráficos dispersos se puede lograr una relación logarítmica. De hecho, para los gráficos dispersos, la estrategia de coloración voraz estándar 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 ordenamiento de vértices dados, se ha definido como una coloración producida por un algoritmo voraz 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 puede obtener para el ordenamiento 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 dado. A pesar de su definición diferente, 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 utilizar pocos colores, el coloreado voraz se puede utilizar en aplicaciones donde se necesita un coloreado de grafos bueno pero no óptimo. Una de las primeras aplicaciones del algoritmo voraz fue en problemas como la programación de cursos, en la que se debe asignar una colección de tareas a un conjunto dado de franjas horarias, evitando que se asignen tareas incompatibles a la misma franja horaria. [4] También se puede utilizar en compiladores para la asignación de registros , aplicándolo a un grafo cuyos vértices representan valores que se asignarán a registros y cuyos bordes representan conflictos entre dos valores que no se pueden asignar al mismo registro. [30] En muchos casos, estos grafos de interferencia son grafos cordales , lo que permite que el coloreado voraz produzca una asignación óptima de registros. [31]
En la teoría de juegos combinatorios , para un juego imparcial dado en forma explícita como un gráfico acíclico dirigido cuyos vértices representan posiciones de juego y cuyos bordes representan movimientos válidos de una posición a otra, el algoritmo de coloración voraz (que utiliza el reverso de un ordenamiento topológico del gráfico) 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 grafo de grado máximo Δ , cualquier coloración voraz utilizará como máximo Δ + 1 colores. El teorema de Brooks establece que con dos excepciones ( camarillas y ciclos impares ) se necesitan como máximo Δ colores. Una prueba del teorema de Brooks implica encontrar un ordenamiento 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 que no sea el último tenga al menos un vecino posterior. Para un ordenamiento con esta propiedad, el algoritmo de coloración voraz utiliza como máximo Δ colores. [33]
