El problema del viajante con grafos

Abstract

Este Trabajo Fin de Grado en Matemáticas aborda el problema del viajante, un problema clásico de optimización combinatoria que responde a la siguiente pregunta: dada una lista de posibles ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible para visitar cada ciudad exactamente una vez y al finalizar regresar a la ciudad origen? El problema es modelizado mediante grafos, cuya teoría se desarrolla a lo largo del trabajo. El problema del viajante es muy difícil de resolver en la práctica de forma efectiva y en un tiempo razonable, a pesar de la apariencia del mismo. Debido a ello, se desarrolla la teoría de la complejidad computacional y se utilizan algoritmos aproximados para su resolución, siendo el de Christofides el principal algoritmo de resolución empleado en elpresente trabajo.