Grafos hamiltonianos en el diseño de viajes

• Autores: Cristina Jordán Lluch , Esther Sanabria Codesal
• Localización: Modelling in Science Education and Learning, ISSN-e 1988-3145, Vol. 6, Nº. 2, 2013 (Ejemplar dedicado a: Número 2. Junio 2013), págs. 133-143
• Idioma: español
• DOI: 10.4995/msel.2013.1941
• Enlaces
  • Texto completo
• Resumen
  • español

    La existencia y, en su caso, localización de caminos con diferentes propiedades es un tema recurrente en la teoría de grafos. Uno de estos problemas consiste en encontrar recorridos que pasen por varios puntos, una sola vez, empezando y terminando en un mismo lugar. La parte de la teoría de grafos que resuelve este problema es la teoría de ciclos hamiltonianos. Si no exigimos coincidencia de los extremos del recorrido obtenemos una variante de este problema, que podemos resolver con lo que se conoce como caminos hamiltonianos. En el presente trabajo centramos nuestra atención en problemas con contextos reales, relacionados con el diseño de itinerarios turísticos en un viaje, cuya solución se obtenga, tras una modelización adecuada, localizando este tipo de caminos. Los abordaremos estudiando transformaciones adecuadas del grafo G elegido para representar la situación planteada, de manera que, del análisis de la existencia de ciclos hamiltonianos en el nuevo grafo auxiliar G0, podamos determinar la existencia de caminos hamiltonianos en el grafo G y, caso de existir, encontrar al menos uno.

  • English

    The existence and, if applicable, the location of paths with given properties is a topic in graph theory. One of these problems is to find routes through all points, only once, starting and ending at the same node. This problem is known in Graph Theory as the theory of Hamilton cycles. If the concurrence of the initial and final ends is not required then we have a version of this problem known as the Hamiltonian path problem. In this article we focus on some real situation problems related to design tourist routes on a journey. Their solutions are obtained after a proper modelling. We study appropriate transformations of the graph G chosen to represent the situation so that we could determine the existence of Hamiltonian paths in the graph G and, if available, to find at least one of them from the analysis of the existence or not of Hamiltonian cycles in the new auxiliary graph G0.

• Referencias bibliográficas
  • R. Bellman. Dynamic programming treatment of the travelling salesman problem Journal of the ACM 9, 61-63 (1962). http://dx.doi.org/10.1145/321105.321111
  • J. L. Gross, J. Yellen. Graph theory and its applications CRC Press cop. (1999).
  • M. Held, R. M. Karp. A dynamic programming approach to sequencing problems J. SIAM 10(1) 196-210 (1962).
  • C. Jordán.Materiales docentes de la asignatura Estructuras Matemáticas para la Informática II
  • C. Jordán, J.R. Torregrosa. Introducción a la teoría de grafos y sus algoritmos Reverté-UPV, Spain (1996).
  • F. Rubin. A Search Procedure for Hamilton Paths and Circuits Journal of the ACM, 21 576-80 (1974).