4.3.6. Otros problemas con grafos.
Un grafo no dirigido G representa elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
La coloración de un grafo consiste en la asignación de un color (o etiqueta) a cada nodo, de forma que dos nodos incompatibles no tengan el mismo color.
Problema de coloración de grafos:
Realizar una coloración del grafo utilizando un número mínimo de colores.
Ejemplo. Un grafo se emplea para representar trayectorias (en una intersec-ción de calles) e incompatibilidades entre ellas. El objetivo es diseñar un sistema de semáforos con un número mínimo de estados. Cada estado será un color resultante del algoritmo de coloración.
La coloración de grafos es un problema NP-completo.