Grafos hamiltonianos en el diseño de viajes

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.