Grafos hamiltonianos aplicado al turismo de Panamá.

Julio Enrique Trujillo González^1*

1.Profesor, Facult= ad de Ingeniería y Tecnología, Universidad Católica Santa María la Antigua y Facultad de Ciencias Naturales, Exactas y Tecnología, Universidad de Panamá= .

*Autor para correspondencia. Email: julioetrujillog@gmail.com

Recibido: 18 de febrero de 2019=

Aceptado: 15 de mar= zo de 2019

______________________= _______________________________________________________________Resumen

Un problema clásico de Teoría de Grafos es encontrar un camino que pase por varios puntos, sólo una vez, empezando y terminando en un lugar (camino hamiltoniano). Al agregar la condición de que sea la ruta más corta, el problema se convierte uno de tipo TSP (Traveling Salesman Problem). En este trabajo nos centraremos en un problema de tour turístico por la ciudad de Panamá, transformándolo a un problema de grafo de tal manera que represente la situación planteada.

Palabras clave: Gr= afos, ciclo hamiltoniano, camino hamiltonia, Traveling Salesman Problem. <= span lang=3DES style=3D'font-family:"Garamond",serif;mso-bidi-font-family:"Times= New Roman"'>

Abstract

A classic problem of Graph Theory is to find a path that passes through several points, only onc= e, starting and ending in one place (hamiltonian path). When adding the condit= ion that it is the shortest route, the problem becomes one of type TSP (Traveli= ng Salesman Problem). In this paper we will focus on a tourist tour problem in= the city of Panama, transforming it into a graph problem in such a way as to represent the situation posed.

Keywords: Hamiltonian cycle, Hamiltonian path, Traveling Salesman Problem.

1 Introducción

. Nuestro objetivo= es mostrar la importancia de la modelización y como utilizar algoritmos para resolver el problema. Trataremos un problema ilustrativo, lo llevaremos a un problema de grafos, para analizar la existencia de tours. Utilizaremos programas hechos por el autor en C++ para obtener una solución. =

2 Conceptos básicos

G consiste de un conjunto finito no vacío = de elementos llamados vértices (o nodos)= , y un conjunto finito <= /span>de pares sin orden de elementos de llamados aristas. También se suele defin= ir como una triada donde

{u,v} o por .

G<= ![endif]--> mediante un diagrama de puntos (vértices= ) y líneas (aristas).

G es un conjunto finito de aristas de la f= orma en el cual dos aristas son adyacentes o idénticas. Si se dice que el camino es un ciclo y el r= esto de vértices son distintos entres ellos y con , llamamos ciclo hamiltoniano si el ciclo contiene todos los vértices del grafo y de manera análoga, un camino es hamilt= oniano si pasa por todos los vértices sólo una vez. Por último, un grafo es hamiltoniano si posee un ciclo hamiltoniano.

Teorema 1G es un grafo simple con = vértices, y

v<= ![endif]--> y , then es Hamiltoniano.

grad:V= G→N nos dice cuantos vértices se conectan co= n el vértice , es decir, es el cardinal del conj= unto es un grafo simple con = vértices, y si

para cada vértice , entonces es Hamiltoniano.

Teorema 3G un grafo no dirigido. Existe un camino hamiltoniano en si y sólo si es hamiltoniano, donde y .

H<= ![endif]--> en con extremo y . Este camino también le pertenece = a (ver Fig 2.), basta ańadir y para tener un ciclo hamiltoniano en .

<= span lang=3DES style=3D'font-family:"Garamond",serif'>

Fig. 1 Ciclo hamiltoniano. Fig. 2 Camino hamiltoniano<= /o:p>

W<= ![endif]--> en , eliminando obtenemos un camino hamiltoniano como el= que aparece en Fig 1.

3 Tour por la capital de Panamá

Tabla 1. Distancias entre puntos<= o:p>

G<= ![endif]--> con

los puntos turísticos a visitar y representa la ruta entre el punto turíst= ico y el punto turístico , además asumimos que podemos ir en= los sentidos, es decir que e representa la misma ruta.

1. = G<= ![endif]--> con y como se definió al principio. El nuevo g= rafo con y con 10-lugar turístico ficticio cuya dis= tancia a todos los demás puntos son igual a 10 km. Obtenemos la solución: <= !--[if gte msEquation 12]>9-8-2-3-5-1-7-6-4 con distancia 58.8 km.

2. = En este caso el grafo no posee ciclo hamiltoniano y tampoco ca= mino hamiltoniano.

3. = 4. =

4 Conclusiones

5 Bibliografía

Bapat, R.B. Graps and Matrices. Springer. Universitext. 2010.

Bondy, J. A; Murty, U.S. = Graph Theory with Applications.North-Holla= nd. Estados Unidos de América 1982.

Diestel, Reinhard. Graph The= ory. Springer-Verlag. Segunda Edición. Estados Unidos = de América. 2000

Gibbons, Alan. Algorithmic Graph Theory. Cambr= idge University Press. Estados Unidos de América. Ray, Saha Santanu. Graph The= ory with Algorithms and its Applications, In Applied Science and Technology. Springer. Estados Unidos de América. 2013.

Wilson, Robin. Introduct= ion to Graph Theory. Addison Wesley Longman Limited.C= arta Edición. Inglatera. 1996. =