ESTUDIO COMPARATIVO DE ALGORITMOS PARA LA RESOLUCIÓN DEL PROBLEMA DE COLORACIÓN DE GRAFOS

Abstract

Este Trabajo de Fin de Grado se centra en el estudio del problema del coloreado de grafos, una tarea fundamental en la teoría de grafos con múltiples aplicaciones en campos como la planificación, la asignación de recursos y las redes de comunicación. El objetivo principal del problema consiste en asignar colores a los vértices de un grafo de forma que no haya dos vértices adyacentes con el mismo color, minimizando al mismo tiempo el número total de colores utilizados.

Para abordar este problema, se analizan y comparan tres enfoques diferentes. El primero es el algoritmo greedy y una variante greedy mejorada, que aplican reglas heurísticas sencillas y rápidas para asignar colores, aunque sin garantizar una solución óptima. El segundo enfoque se basa en la técnica del cutwidth, que consiste en encontrar un ordenamiento lineal de los vértices que minimice el número máximo de aristas cruzadas, con el objetivo de facilitar un coloreado más eficiente. Por último, se implementa una solución metaheurística mediante el uso del algoritmo de colonia de hormigas, inspirado en el comportamiento cooperativo de las hormigas para encontrar soluciones óptimas en problemas de optimización combinatoria.

El trabajo incluye una implementación práctica de los tres métodos y una evaluación comparativa sobre distintos grafos de prueba. Los resultados muestran las ventajas y limitaciones de cada enfoque en términos de calidad del coloreado y tiempo de ejecución. Finalmente, se discuten posibles mejoras y futuras líneas de investigación para optimizar aún más la resolución del problema del coloreado de grafos.