- -

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

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

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

Show simple item record

Files in this item

dc.contributor.author Jordan, Cristina es_ES
dc.contributor.author Burriel, Jordi es_ES
dc.contributor.author Herráiz, Raquel es_ES
dc.date.accessioned 2018-04-24T10:17:18Z
dc.date.available 2018-04-24T10:17:18Z
dc.date.issued 2011-06-05
dc.identifier.uri http://hdl.handle.net/10251/100937
dc.description.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_ES
dc.description.abstract [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. es_ES
dc.language Español es_ES
dc.publisher Universitat Politècnica de València
dc.relation.ispartof Modelling in Science Education and Learning
dc.rights Reconocimiento - No comercial (by-nc) es_ES
dc.subject Grafo ponderado es_ES
dc.subject Algoritmo de Floyd es_ES
dc.subject Problema camino más cortos es_ES
dc.title Un problema a resolver con los algoritmos de caminos más cortos es_ES
dc.type Artículo es_ES
dc.date.updated 2018-04-23T11:52:11Z
dc.identifier.doi 10.4995/msel.2011.3086
dc.rights.accessRights Abierto es_ES
dc.description.bibliographicCitation Jordan, C.; Burriel, J.; Herráiz, R. (2011). Un problema a resolver con los algoritmos de caminos más cortos. Modelling in Science Education and Learning. 4:263-273. doi:10.4995/msel.2011.3086 es_ES
dc.description.accrualMethod SWORD es_ES
dc.relation.publisherversion https://doi.org/10.4995/msel.2011.3086 es_ES
dc.description.upvformatpinicio 263 es_ES
dc.description.upvformatpfin 273 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 4
dc.identifier.eissn 1988-3145


This item appears in the following Collection(s)

Show simple item record