4.4.2. Coloración de grafos.
Problema: dado un grafo no dirigido, realizar una coloración utilizando el número mínimo de colores.
Coloración: asignación de un color a cada nodo, de forma que dos nodos unidos con un arco tengan siempre distinto color.
- Una solución será un conjunto de pares de la forma (nodo, color) cumpliendo que para todo (ni, ci) y (nj, cj), si (ni, nj) es una arista del grafo, entonces ci ? cj.
- Podemos usar una heurística voraz para obtener una solución:
- Empezar con un color c1, y todos los nodos sin colorear.
- Para cada uno de los nodos que no tienen asignado un color, comprobar si es posible asignarles el color actual. Repetir hasta comprobar todos los candidatos.
- Si quedan nodos sin colorear, escoger otro color y volver al paso anterior.