Solucionador de Coloración de Grafos

Pseudocódigo

La coloración voraz son tres líneas y siempre produce una coloración válida. Lo que no produce necesariamente es una mínima, y el orden de los vértices decide cuánto se acerca.

ColoracionVoraz(grafo, orden):
    color = {}
    para cada vértice v en orden:
        usados = { color[n] : n vecino de v, ya coloreado }
        c = el menor entero positivo que no esté en usados
        color[v] = c
    devolver color

// Welsh-Powell: ordenar por grado descendente
// DSatur: elegir repetidamente el vértice sin colorear con
//         más colores distintos entre sus vecinos (saturación),
//         desempatando por grado

El voraz nunca usa más de grado máximo más uno colores, porque al llegar a un vértice este tiene a lo sumo esa cantidad de vecinos y por tanto esa cantidad de colores prohibidos. Es una garantía real, pero puede quedar muy lejos del número cromático verdadero. DSatur es la mejora práctica: elegir a continuación el vértice más restringido es exactamente la heurística que evita acorralarte.

Ejemplo resuelto, paso a paso

Colorea un ciclo de cinco vértices de forma voraz en orden alfabético y después contrasta el resultado con el número cromático real.

Grafo de ejemplo: Ciclo no dirigido A-B, B-C, C-D, D-E y E-A.

1. Colorear A. Ningún vecino está coloreado todavía, así que A toma el color 1.
2. Colorear B. B es adyacente a A, que tiene el color 1, así que el menor disponible es el color 2.
3. Colorear C. C es adyacente a B (color 2) y al todavía incoloro D. El color 1 está libre, así que C toma el 1.
4. Colorear D. D es adyacente a C (color 1) y al incoloro E. El color 2 está libre, así que D toma el 2.
5. Colorear E fuerza un tercero. E es adyacente a D (color 2) y a A (color 1). Ambos colores existentes están ocupados, así que E necesita el color 3.

La coloración es A 1, B 2, C 1, D 2, E 3, con tres colores, y la fuerza bruta confirma que el número cromático de un ciclo de cinco es efectivamente 3. Aquí el voraz resultó óptimo. La razón de que hagan falta tres es que el ciclo tiene longitud impar: los colores deben alternarse alrededor de un ciclo, y un ciclo impar te devuelve al inicio necesitando un color distinto del que ya está. Todo ciclo par se conforma con 2.

Complejidad y de dónde sale

Tiempo: O(V + E) el voraz, NP-difícil exacto · Espacio: O(V)

La coloración voraz examina cada vértice una vez e inspecciona cada arista dos veces, una desde cada extremo, así que es O(V + E) con O(V) de espacio para el vector de colores. Ese coste compra una coloración válida que usa a lo sumo grado máximo más uno colores, nunca un mínimo garantizado. Calcular el número cromático real es NP-difícil, e incluso aproximarlo dentro de un factor de V elevado a 1 menos épsilon es NP-difícil, lo cual es inusualmente fuerte: para la mayoría de problemas existe alguna aproximación decente, y para la coloración esencialmente ninguna. Decidir la 2-coloreabilidad es la excepción y es fácil, ya que es exactamente la prueba de bipartición con O(V + E). Decidir la 3-coloreabilidad ya es NP-completo.

Cuándo usar Coloración de Grafos y cuándo no

Elige según cuántos colores esperes necesitar y si exiges el mínimo verdadero.

Errores frecuentes

• Suponer que el voraz da el número cromático. Da una coloración válida, no una mínima, y la diferencia puede ser grande. En el grafo corona con partes {a1,a2,a3} y {b1,b2,b3} donde ai se une a bj siempre que i sea distinto de j, el orden intercalado a1,b1,a2,b2,a3,b3 hace que el voraz use 3 colores aunque el grafo es bipartito y bastan 2. Ordenando ese mismo grafo como a1,a2,a3,b1,b2,b3 se obtienen 2.
• Ignorar cuánto importa el orden de los vértices. Siempre existe algún orden que alcanza el número cromático verdadero, y encontrarlo es tan difícil como el propio problema de coloración. Por eso DSatur elige dinámicamente sobre la marcha en lugar de fijar un orden de antemano.
• Confundir número cromático con número de clique. Un clique de tamaño k obliga a al menos k colores, así que el número de clique es una cota inferior, pero ambos pueden diferir. Los ciclos impares de longitud 5 o más necesitan 3 colores sin contener ningún triángulo.
• Esperar que exista una buena aproximación. A diferencia de muchos problemas NP-difíciles, la coloración de grafos no tiene ninguna aproximación conocida con factor constante y hay resultados de dureza fuertes que hacen improbable que exista. Las heurísticas pueden ir bien en la práctica pero no ofrecen garantía en el peor caso.
• Olvidar que los bucles propios la hacen imposible. Un vértice adyacente a sí mismo nunca puede tener un color distinto del suyo, así que un grafo con un bucle propio no admite ninguna coloración propia. Recházalos antes de empezar.

Preguntas frecuentes

¿Qué es la coloración de grafos?

La coloración de grafos asigna un color a cada vértice de modo que dos vértices adyacentes nunca compartan color. El menor número de colores que funciona es el número cromático del grafo. Modela cualquier problema donde haya que separar elementos en conflicto, como programar exámenes de forma que ningún estudiante tenga dos a la vez.

¿Qué es el número cromático de un grafo?

El mínimo número de colores necesario para una coloración propia. Un grafo bipartito tiene número cromático 2 o menos, un ciclo impar tiene 3, y un grafo completo de n vértices tiene n. Calcularlo en general es NP-difícil, aunque un clique de tamaño k da una cota inferior sencilla de k.

¿El algoritmo voraz usa siempre el mínimo de colores?

No. Siempre produce una coloración válida con a lo sumo grado máximo más uno colores, pero eso puede superar al número cromático. En el grafo corona, un grafo bipartito que solo necesita 2 colores, un orden desafortunado hace que el voraz use 3. Siempre existe un orden que alcanza el óptimo, pero encontrarlo es tan difícil como el problema original.

¿Cuál es la diferencia entre coloración voraz y DSatur?

El voraz fija un orden de vértices de antemano y colorea en ese orden. DSatur elige el siguiente vértice dinámicamente, tomando siempre el que tiene más colores distintos entre sus vecinos y desempatando por grado. Ese enfoque en el vértice más restringido hace que DSatur sea óptimo en grafos bipartitos y mucho mejor en general, a cambio de O(V al cuadrado) en lugar de O(V + E).

¿Para qué se usa la coloración de grafos?

Para la asignación de registros en compiladores, donde los registros son colores y las variables que interfieren son adyacentes. También para horarios de exámenes y turnos, asignación de frecuencias de radio evitando interferencias entre emisores cercanos, resolución de sudokus y separación de tareas en conflicto en cualquier problema de asignación de recursos.