Extensiones del problema de coloración de grafos

Abstract

En este trabajo se presentan extensiones del problema de coloración, al introducir el nuevo requerimiento de que el número de colores no tiene que ser necesariamente el mínimo, esto permite modelizar otros problemas de planificación del tiempo. A este problema se le ha llamado el Problema de Coloración Robusta, y consiste en determinar una coloración con c colores que minimice el grado de rigidez; la rigidez de una coloración distingue las aristas complementarias penalizándolas cuando sus extremos comparten el mismo color. Distintas penalizaciones de las aristas complementarias permiten obtener coloraciones válidas con diferentes propiedades. En particular, se puede considerar el caso en que se añadan nuevas aristas al grafo y el grado de rigidez de la coloración penaliza la incompatibilidad de colores de los extremos de esas aristas añadidas, de ahí el nombre de coloración robusta. Se proponen dos algoritmos para encontrar soluciones aproximadas: uno es de enumeración parcial y el otro es un híbrido de un genético con uno voraz, cuyas soluciones se consideran aceptables después de haber sido comparadas con las exactas,obtenidas de modelos de programación matemática del problema. También se presenta el Problema de Coloración Robusta Generalizado, en que se relaja el concepto de incompatibilidad de una coloración respecto al Problema de Coloración Robusta. Se propone un híbrido de una algoritmo genético y uno voraz con el que se obtienen buenas soluciones. Finalmente se presentan dos generalizaciones difusas del problema de coloración, una basada en la difuminación del concepto de color y otra basada en el concepto de grafo difuso. A partir de este último, se introduce el concepto de número cromático difuso