Diseño de un algoritmo para aproximar el coloreo de una gráfica mediante conjuntos maximales independientes

El problema del coloreo de gráficas por su importancia se ha tratado de solucionar por diferentes algoritmos, entre los más usados se encuentran los heurísticos, los cuales aproximan la solución, además existen diferentes metodologías de solución. En particular, el presente trabajo de Tesis se ha centrado en tres algoritmos heurísticos, el algoritmo greedy de JGraphT, el algoritmo determinista propuesto por Guzmán et al. y las propuestas híbridas de combinar un algoritmo determinista con un algoritmo genético. Derivado de los resultados obtenidos se puede concluir que en términos de n umero de colores las propuestas de Guzmán et al.(Apéndice A) y la que se presenta como trabajo final de tesis son competitivas, debido a que, el promedio de colores obtenidos en 20 ejecuciones, los resultados obtenidos por la propuesta híbrida de esta tesis, son mejores en gran medida que los obtenidos por Guzmán et al. debido a que el número de colores no está disperso con respecto al promedio obtenido, esto se observa en la desviación estándar obtenida para cada prueba. Adicionalmente, de los resultados de coloreo obtenidos por JGraphT el 62.5% excede el coloreo de una a diez unidades de color, mientras que la propuesta de esta Tesis en s olo 45.83% de las instancias el coloreo excede de una a cinco unidades de color, mientras que para Guzmán et al. en un 58.33% el coloreo obtenido excede de una a seis unidades de color. Los resultados obtenidos en esta investigación y concluidos como los que mantienen una mejor aproximación al coloreo, se deben a la implementación de la Fase de regeneración, la cual favoreció en la mayoría de las instancias, que de la gráfica conocida como residual, a que la aproximación al coloreo se cumpliera con el número de colores restantes, es decir el número k conocido como el mejor coloreo obtenido hasta el momento, se le resta el número de MISes extraídos de la primera fase, debido a que los MISes de la fase de extracción son considerados de la completa, dejando una gráfica residual densa, la cual complica que el coloreo sea propio con k-MISes. Por otro lado, de los análisis realizados en la Sección 4 se encuentra el de tiempo de ejecución, donde se muestra el tiempo en segundos que tardó cada algoritmo en obtener una aproximación, de esto se puede concluir que en términos de tiempo de ejecución el algoritmo híbrido propuesto, toma un mayor tiempo de ejecución en comparación con el resto de los algoritmos comparados, debido a que en la fase de regeneración se considera un número de iteraciones para reconstruir un MIS, así como también el volver a implementar la fase completa de coloreo, dentro de la cual el tiempo que se toma en ejecutar la búsqueda Tabú incrementa el tiempo de ejecución. Sin embargo, ya que el objetivo general fue mejorar la aproximación al coloreo, se considera que se cumplió el objetivo y se verificó la hipótesis propuesta.Dada una gráfíca no dirigida G = (V;E) con un conjunto de vértices V y un conjunto de aristas E, el problema del coloreo de gráfícacas consiste en particionar todos los vértices de V en el mínimo número K de conjuntos (colores), con la característica de que cada par de vértices en un conjunto no compartan arista. El problema de coloreo se ha estudiado desde 3 perspectivas, la primera es el problema original, encontrar el mínimo número de colores con los cuales una gráfíca puede ser coloreado, la segunda trata de decidir si una gráfíca es k colorable, mientras que la última, aproxima el coloreo con respecto al mejor valor reportado en la literatura (ya que puede no conocerse el mínimo). Diversas propuestas de algoritmos se han desarrollado de manera exacta o heurísticas. En esta Tesis se propone un algoritmo de tipo heurístico resultado de la combinación de un algoritmo determinista y un algoritmo evolutivo para aproximar el coloreo de gráficas con respecto al mejor valor reportado en la literatura. El algoritmo propuesto se evalúa con un conjunto de gráficas propuestas en la literatura. Los resultados obtenidos validan la viabilidad de la propuesta con respecto a otros algoritmos reportados en la literatura.Conacyt: 702275/58443