Un viatge per la teoria de grafs de la mà de la computació

Abstract

Treball guanyador de la XXII Edició dels premis a Treballs de Recerca de la UdL per a l’estudiantat de batxillerat i cicles formatius de grau superior en l'Àrea Tecnològica. Tutora: Ana Isabel Ibáñez Hernández (Institut Samuel Gili i Gaya de Lleida).

La teoria de grafs és una branca de les matemàtiques que permet modelitzar relacions entre diferents elements a través de vèrtexs i arestes. Un dels problemes més rellevants dins d’aquesta disciplina és el Problema del Viatjant de Comerç (TSP), que consisteix en trobar el recorregut més curt que permeti visitar una sèrie de punts o ciutats una sola vegada i retornar al punt de partida. Aquest problema és especialment complex quan el nombre de punts augmenta. Tot i la rellevància del TSP en aquest treball, ja que és la base de la hipòtesi que es vol demostrar, també s’hi aborden els conceptes bàsics de la teoria de grafs i les seves aplicacions, juntament amb l’estudi dels principals teoremes que caracteritzen els grafs hamiltonians i eulerians. El treball, a més, mostra com el Problema del Viatjant de Comerç es pot traduir al llenguatge de grafs a partir de l’estudi dels grafs hamiltonians. Pel que fa a la part pràctica, s’ha desenvolupat un programa en Python, barrejant diferents algoritmes existents, amb algunes implementacions de creació pròpia, per resoldre el TSP aplicat als punts d’interès turístic de la ciutat de Lleida. L’algoritme creat té com a objectiu trobar una ruta que minimitzi la distància total recorreguda passant per tots els punts només un cop. L’algoritme, però, no garanteix l’assoliment de la solució més òptima, ja que prioritza una menor complexitat temporal (time complexity) front a altres algoritmes que tarden molt temps o, en el cas de grafs molt complexos, no troben cap solució. L’algortime resultant permet generar solucions de manera eficient en escenaris amb diversos punts a visitar, assegurant que no es repeteixi cap punt durant el recorregut.

Graph theory is a branch of mathematics that allows modeling relationships between different elements through vertices and edges. One of the most relevant problems within this discipline is the Traveling Salesman Problem (TSP), which consists of finding the shortest route that allows visiting a series of points or cities once and returning to the starting point. This problem becomes particularly complex as the number of points increases. Despite the relevance of the TSP in this work, as it is the basis of the hypothesis to be demonstrated, the basic concepts of graph theory and its applications are also addressed, along with the study of the main theorems characterizing Hamiltonian and Eulerian graphs. Furthermore, this work shows how the Traveling Salesman Problem can be translated into graph language through the study of Hamiltonian graphs. Regarding the practical part, a program has been developed in Python, combining different existing algorithms, with some personal implementations, to solve the TSP applied to the points of interest in the city of Lleida. The created algorithm aims to find a route that minimizes the total distance traveled while visiting all points only once. However, the algorithm does not guarantee achieving the most optimal solution, as it prioritizes lower time complexity over other algorithms that may take a long time or, in the case of very complex graphs, may not find a solution at all. The resulting algorithm allows the generation of efficient solutions in scenarios with multiple points to visit, ensuring that no point is repeated during the journey.