Colorear un grafo consiste en asignar colores a sus vértices sin repetir color entre vecinos. El desafío es satisfacer todas las restricciones utilizando la menor cantidad posible de colores.
La coloración modela conflictos. Si dos actividades no pueden usar simultáneamente el mismo recurso, se conectan mediante una arista y deben recibir colores diferentes.
Los colores son etiquetas abstractas: pueden representar horarios, frecuencias, registros, aulas o cualquier conjunto de recursos incompatibles.
Una coloración propia asigna un color c(v) a cada vértice de modo que los extremos de toda arista tengan colores distintos.
Los vértices que no son adyacentes pueden compartir color, aunque estén conectados indirectamente mediante un camino.
El número cromático χ(G) es la menor cantidad de colores necesaria para obtener una coloración propia.
Encontrar cualquier coloración válida es sencillo; demostrar que utiliza la cantidad mínima puede ser mucho más difícil.
| Grafo | Número cromático | Motivo |
|---|---|---|
| Sin aristas | 1 | No existen conflictos |
| Árbol con alguna arista | 2 | Es bipartito |
| Ciclo par | 2 | Los colores alternan |
| Ciclo impar | 3 | Dos colores producen un conflicto al cerrar |
| Completo Kn | n | Todos los vértices son vecinos |
El algoritmo voraz procesa los vértices en algún orden y asigna a cada uno el color disponible de menor índice.
Siempre produce una coloración válida, pero no necesariamente óptima.
Este grafo es bipartito y puede colorearse con 2 colores. Compara el orden por particiones con el orden intercalado, que obliga al algoritmo voraz a utilizar 3.
Orden de procesamiento
Vecinos coloreados
Acción actual
El resultado con 3 colores sigue siendo válido, pero no es mínimo. Cambiar solamente el orden mejora la solución sin cambiar la regla voraz.
function colorearVoraz(grafo, orden) {
const color = {};
for (const vertice of orden) {
const usados = new Set();
for (const vecino of grafo[vertice]) {
if (color[vecino] !== undefined) usados.add(color[vecino]);
}
let candidato = 0;
while (usados.has(candidato)) candidato++;
color[vertice] = candidato;
}
return color;
}Con un orden afortunado, el algoritmo voraz puede usar χ(G) colores. Con otro puede utilizar muchos más, incluso en grafos que admiten solo dos colores.
Ordenar los vértices por grado descendente suele ayudar porque resuelve primero los más restrictivos, pero continúa siendo una heurística sin garantía de optimalidad.
Las cotas permiten evaluar una solución aunque no conozcamos el óptimo exacto.
ω(G) es el tamaño de la clique máxima: sus vértices requieren colores distintos. Δ(G) es el grado máximo; el algoritmo voraz nunca necesita más de Δ + 1 colores.
Un grafo con al menos una arista es bipartito si y solo si puede colorearse con dos colores. BFS o DFS asigna colores alternos y detecta cualquier conflicto.
color[origen] = 0;
while (cola.length) {
const u = cola.shift();
for (const v of grafo[u]) {
if (color[v] === undefined) {
color[v] = 1 - color[u];
cola.push(v);
} else if (color[v] === color[u]) {
return false; // existe un ciclo impar
}
}
}Todo árbol con más de un vértice tiene número cromático 2: basta alternar colores según la paridad de la distancia a una raíz.
Un ciclo par también requiere 2 colores. Un ciclo impar necesita 3 porque la alternancia regresa al inicio con el mismo color en ambos extremos de la última arista.
En una clique de tamaño k, cada vértice es vecino de los otros k − 1. Por ello hacen falta al menos k colores diferentes.
Sin embargo, χ(G) puede superar el tamaño de la clique máxima. Las cliques proporcionan una cota inferior, no siempre el valor exacto.
El teorema de los cuatro colores afirma que todo grafo planar admite una coloración con a lo sumo cuatro colores.
En la interpretación de mapas, cada región se convierte en un vértice y se conectan regiones que comparten un segmento de frontera. Tocar únicamente en un punto no crea adyacencia.
Decidir si un grafo puede colorearse con k colores es NP-completo para k ≥ 3. Calcular χ(G) exactamente es NP-difícil.
Para grafos grandes se utilizan heurísticas, aproximaciones o algoritmos exactos exponenciales cuando el tamaño permite explorar combinaciones.
Para decidir si existe una k-coloración, el backtracking asigna colores uno por uno y retrocede cuando ningún color es válido.
function intentar(posicion, orden, grafo, colores, k) {
if (posicion === orden.length) return true;
const u = orden[posicion];
for (let c = 0; c < k; c++) {
if (grafo[u].every(v => colores[v] !== c)) {
colores[u] = c;
if (intentar(posicion + 1, orden, grafo, colores, k)) return true;
delete colores[u];
}
}
return false;
}DSATUR selecciona en cada paso el vértice no coloreado con mayor grado de saturación: la cantidad de colores distintos presentes entre sus vecinos.
Los empates suelen resolverse por mayor grado. Esta estrategia presta atención a las restricciones actuales y normalmente supera al orden fijo por grado.
En la coloración de aristas, dos aristas incidentes no pueden compartir color. Puede transformarse en coloración de vértices construyendo el grafo línea L(G), donde cada arista original se convierte en un vértice.
Es útil para programar comunicaciones o tareas que comparten un recurso en sus extremos.
La coloración expresa incompatibilidades mediante una regla local muy simple, pero optimizar la cantidad de colores conduce a un problema computacionalmente difícil. Por eso conviven algoritmos exactos, cotas y heurísticas.
En el próximo tema estudiaremos el problema del viajante, otra optimización combinatoria difícil donde el objetivo será encontrar un recorrido cerrado de costo mínimo.