MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_NextPart_01D5C645.F27EFFB0" Este documento es una página web de un solo archivo, también conocido como archivo de almacenamiento web. Si está viendo este mensaje, su explorador o editor no admite archivos de almacenamiento web. Descargue un explorador que admita este tipo de archivos, como Windows® Internet Explorer®. ------=_NextPart_01D5C645.F27EFFB0 Content-Location: file:///C:/C9124321/file7249.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="windows-1252"

Grafos hamiltonianos aplicado al turismo de Panamá.

 

Julio Enrique Trujillo González1*

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 .