Grafos hamiltonianos en el diseño de viajes

Abstract

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.

Keywords

• Graphs
• Hamiltonian cycle
• Hamiltonian path
• Hamiltonian graph
• Modelling