Extensiones del problema de coloración de grafos

En este trabajo se presentan extensiones del problema de coloracion, al introducir el nuevo requerimiento de que el numero de colores no tiene que ser necesariamente el minimo, esto permite modelizar otros problemas de planificacion del tiempo. A este problema se le ha llamado el Problema de Coloracion Robusta, y consiste en determinar una coloracion con c colores que minimice el grado de rigidez; la rigidez de una coloracion distingue las aristas complementarias penalizandolas cuando sus extremos comparten el mismo color. Distintas penalizaciones de las aristas complementarias permiten obtener coloraciones validas con diferentes propiedades. En particular, se puede considerar el caso en que se anadan nuevas aristas al grafo y el grado de rigidez de la coloracion penaliza la incompatibilidad de colores de los extremos de esas aristas anadidas, de ahi el nombre de coloracion robusta. Se proponen dos algoritmos para encontrar soluciones aproximadas: uno es de enumeracion parcial y el otro es un hibrido de un genetico con uno voraz, cuyas soluciones se consideran aceptables despues de haber sido comparadas con las exactas,obtenidas de modelos de programacion matematica del problema. Tambien se presenta el Problema de Coloracion Robusta Generalizado, en que se relaja el concepto de incompatibilidad de una coloracion respecto al Problema de Coloracion Robusta. Se propone un hibrido de una algoritmo genetico y uno voraz con el que se obtienen buenas soluciones. Finalmente se presentan dos generalizaciones difusas del problema de coloracion, una basada en la difuminacion del concepto de color y otra basada en el concepto de grafo difuso. A partir de este ultimo, se introduce el concepto de numero cromatico difuso