Un problema a resolver con los algoritmos de caminos más cortos

Abstract

[EN] Graph theory solves, via a good modelization, a very large number of problems in different areas. This is why, this theory has been having an exponential increase in the last years. One of the basic problems that this theory solves is to obtain the shortest path between two points. In order to illustrate this problem, to motivate its study and to introduce the student in the world of the mathematical modelization and its large range of possibilities, we present a specific case: to help the police to catch the authors of a theft. The solution consists of representing the city where it took place by a no directed positive weighted graph and to apply the Floyd’s algorithm mixed with a reasoning of combinatorial type. At the end of the exercise, we can assure that the thieves cannot escape, by using another concept of graph theory, the vertex-cut.

[ES] Numerosos problemas pertenecientes a los más diversos campos pueden ser resueltos a partir de la modelización en teoría de grafos, materia en pleno auge, podríamos decir que con crecimiento exponencial, por su amplia aplicabilidad. Uno de los primeros problemas que se plantean al alumno que inicia el estudio de la teoría de grafos es el cálculo del trazado de un camino de mínimo peso de un vértice a otro, es decir, el cálculo de la distancia mínima que separa dos vértices dados, así como el recorrido a realizar para obtenerla. Para ilustrarlo, motivar su estudio e iniciar al estudiante en el mundo de la modelización y su amplia gama de posibilidades, presentamos el siguiente caso concreto, en el que ayudamos a la policía a atrapar a los autores de un robo. La solución consiste en representar la ciudad en la que tiene lugar el atraco mediante un grafo no dirigido ponderado positivo, y aplicar el algoritmo de Floyd, entrelazado con razonamientos de tipo combinatorio. Podremos asegurar al final del ejercicio que los ladrones no tienen escapatoria, relacionando la solución con otro concepto de la teoría de grafos, la cortadura de vértices.