Resumen del trabajo fin de master



Título: El problema de coloración de grafos: implementación y/o cooperación
Universidad que ofrece el proyecto: Universidade da Coruña
Director/a:
Lorenzo Freire, Silvia María
Resumen:
Uno de los problemas más conocidos de Teoría de Grafos es el problema de coloración de grafos. Tal y como indica su nombre, se trata de asignar etiquetas denominadas colores a los elementos de un grafo. Hay varios tipos de problemas de coloración de grafos; siendo el más conocido el problema de coloración de los vértices de un grafo. El objetivo en estos problemas es asignar colores a los vértices de un grafo, de tal forma que los vértices adyacentes no compartan el mismo color. Suele ser habitual además buscar el número cromático, que sería el mínimo número de colores necesario para la coloración del grafo. Los problemas de coloración de grafos tienen múltiples aplicaciones. De hecho, se pueden utilizar para resolver muchos problemas de asignación. En función de las características y preferencias del estudiante, se proponen las siguientes opciones a elegir para la realización de un trabajo fin de máster: • Implementar los principales algoritmos de coloración de grafos. • Resolver problemas de asignación haciendo uso de algoritmos de coloración de grafos. • Hacer una revisión bibliográfica de los principales resultados de Teoría de Juegos relacionados con este problema.