Grafos hamiltonianos en el diseño de viajes

Cristina Jordán Lluch, Esther Sanabria Codesal

Resumen

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.

Palabras clave

Grafos; Ciclo hamiltoniano; Camino hamiltoniano; Grafo hamiltoniano; Modelización

Texto completo:

PDF

Referencias

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).

Abstract Views

2024
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