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

Cristina Jordán Lluch, Jordi Burriel, Raquel Herráiz

Resumen

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.


Palabras clave

Grafo ponderado; Algoritmo de Floyd; Problema camino más cortos

Texto completo:

PDF

Referencias

Ralph P. Grimaldi, Matemáticas discretas y combinatoria, Ed. Addison Wesley Longman (1998).

J. L. Gross, J. Yellen, Graph theory and its applications, Chapman&Hall, (2006).

Cristina Jordán, Juan R. Torregrosa, Introducción a la teoría de grafos y sus algoritmos, Ed. Reverté, Valencia, (1996).

Kenneth Rosen, Matemática discreta y sus aplicaciones, Ed. McGrawHill, (2004).

Abstract Views

1304
Metrics Loading ...

Metrics powered by PLOS ALM




Esta revista esta bajo una Licencia licencia de Creative Commons Reconocimiento-NoComercial 4.0 Internacional

Universitat Politècnica de València

e-ISSN: 1988-3145   https://dx.doi.org/10.4995/msel