Algunos algoritmos heurísticos para la coloración de vértices en grafos.

Abstract

Este proyecto de grado investiga cuatro algoritmos heurísticos para la coloración de vértices en grafos, cuyo problema derivó de la coloración de mapas y el teorema de los cuatro colores, en el cual se desarrolló una extensión del problema a grafos simples no dirigidos, que consiste en colorear los vértices de tal manera que los adyacentes no compartan el mismo color, buscando la mínima cantidad de colores posibles, llamado el número cromático del grafo. El documento se organiza en cuatro capítulos, el primero abarca las nociones básicas de teoría de grafos; en el segundo se presentan cotas inferiores y superiores para el número cromático. En el tercer capítulo se analizan los algoritmos Greedy, Largest First, Recursive Largest First y Smallest Last, incluyendo para cada uno su descripción, ejemplos de su ejecución, un pseudocódigo y código de programación en Python. Además, se expone el análisis de un experimento computacional que compara los algoritmos en tres criterios: calidad cromática, desempeño y tiempo computacional. La investigación culmina con dos aplicaciones de la coloración de vértices en grafos: la resolución de sudokus y organización de horarios, mostrando la modelación del problema y la implementación de los algoritmos para su solución.