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
Notación.
Las aristas se denotan por
o por
.
Su
suele representar el grafo
mediante un diagrama de puntos (vértices=
) y
líneas (aristas).
Un
camino en
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.
Para
obtener un camino hamiltoniano basta considerar el problema de los ciclos
hamiltonianos. Para eso enunciaremos algunos teoremas que nos ayudara,
Teorema 1
(Ore, 1960) Si
es un grafo simple con =
vértices, y
Para
cada par de no adyacentes vértices
y
, then
es Hamiltoniano.
La
funció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.
El
teorema 2 nos da las condiciones para la existencia de un ciclo hamiltonian=
o.
Ver (Diestel, 2000)
Otro
resultado que nos dirá sobre la existencia sobre un ciclo hamiltoniano es el
siguiente:
Teorema 3
Sea
un grafo no dirigido. Existe un camino
hamiltoniano en
si y sólo si
es hamiltoniano, donde
y
.
Bosquejo
de prueba.
Siguiendo
la Fig 1. Supongamos que existe un camino hamiltoniano
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>
Supongamos
que existe el ciclo hamiltoniano (ver Fig 2.)
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.
Aplicando
un programa elaborado en C++ nos proporciona la siguiente solución: =
o:p>
Con
una distancia total de 88.09 km.
Podemos
suponer varias escenas:
1. =
El
punto de inicial y final puede ser cualquier lugar turístico. Entonces pode=
mos
utilizar el teorema 3, para incorporar un lugar turístico ficticio que se
conecta con los demás lugares, para determinar un ciclo hamiltoniano. =
Vamos
a considerar el grafo
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. =
El
punto inicial y final lo cambiamos por temporada. Ejemplo: Iniciamos en 3 y
terminamos en 7, debemos agregar dos nuevas aristas que son {3, 10} y {7,10=
},
donde 10 representa el lugar turístico ficticio. En este caso el grafo
no posee ciclo hamiltoniano y tampoco ca=
mino
hamiltoniano.
3. =
Podemos
eliminar puntos turísticos e incorporar nuevos puntos turísticos.
4. =
Dos
o más rutas con puntos en común.
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. =
=
=
=
------=_NextPart_01D5C645.F27EFFB0
Content-Location: file:///C:/C9124321/file7249_archivos/themedata.thmx
Content-Transfer-Encoding: base64
Content-Type: application/vnd.ms-officetheme
UEsDBBQABgAIAAAAIQDp3g+//wAAABwCAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbKyRy07DMBBF
90j8g+UtSpyyQAgl6YLHjseifMDImSQWydiyp1X790zSVEKoIBZsLNkz954743K9Hwe1w5icp0qv
8kIrJOsbR12l3zdP2a1WiYEaGDxhpQ+Y9Lq+vCg3h4BJiZpSpXvmcGdMsj2OkHIfkKTS+jgCyzV2
JoD9gA7NdVHcGOuJkTjjyUPX5QO2sB1YPe7l+Zgk4pC0uj82TqxKQwiDs8CS1Oyo+UbJFkIuyrkn
9S6kK4mhzVnCVPkZsOheZTXRNajeIPILjBLDsAyJX89nIBkt5r87nons29ZZbLzdjrKOfDZezE7B
/xRg9T/oE9PMf1t/AgAA//8DAFBLAwQUAAYACAAAACEApdan58AAAAA2AQAACwAAAF9yZWxzLy5y
ZWxzhI/PasMwDIfvhb2D0X1R0sMYJXYvpZBDL6N9AOEof2giG9sb69tPxwYKuwiEpO/3qT3+rov5
4ZTnIBaaqgbD4kM/y2jhdj2/f4LJhaSnJQhbeHCGo3vbtV+8UNGjPM0xG6VItjCVEg+I2U+8Uq5C
ZNHJENJKRds0YiR/p5FxX9cfmJ4Z4DZM0/UWUtc3YK6PqMn/s8MwzJ5PwX+vLOVFBG43lExp5GKh
qC/jU72QqGWq1B7Qtbj51v0BAAD//wMAUEsDBBQABgAIAAAAIQBreZYWgwAAAIoAAAAcAAAAdGhl
bWUvdGhlbWUvdGhlbWVNYW5hZ2VyLnhtbAzMTQrDIBBA4X2hd5DZN2O7KEVissuuu/YAQ5waQceg
0p/b1+XjgzfO3xTVm0sNWSycBw2KZc0uiLfwfCynG6jaSBzFLGzhxxXm6XgYybSNE99JyHNRfSPV
kIWttd0g1rUr1SHvLN1euSRqPYtHV+jT9yniResrJgoCOP0BAAD//wMAUEsDBBQABgAIAAAAIQB6
ti0ExAYAAI8aAAAWAAAAdGhlbWUvdGhlbWUvdGhlbWUxLnhtbOxZ3W7bNhS+H7B3EHTv+k/yT1Cn
sGU73Zq0Re126yUt0xIbSjREOqlRFNgTDBjQDbsZsLtd7KbA9kwdtu4hdkjJMmnTTRNkQDEsBgKJ
+s7hx3PI71Di3XsvE+pc4IwTlvbc+p2a6+A0ZHOSRj336XRc6bgOFyidI8pS3HPXmLv3jj//7C46
EjFOsAP2KT9CPTcWYnlUrfIQmhG/w5Y4hWcLliVIwG0WVecZugS/Ca02arVWNUEkdZ0UJeB2CjbO
HDuPFgsSYvd4435EoY9UcNkQ0mwinePCRsPOz+sSwdc8oJlzgWjPhZ7m7HKKXwrXoYgLeNBza+rP
rR7fraKjwoiKA7aa3Vj9FXaFwfy8ofrMolnZqef5Xqtf+lcAKvZxo/aoNWqV/hQAhSGMNOdi+mw3
Aq/AaqD80uJ72B426wZe89/c49z35c/AK1Du39vDj8cBRNHAK1CO9/fw/qA7GJr+FSjHt/bw7Vp/
6LUN/woUU5Ke76FrfqsZbEZbQhaM3rfCu743bjcK51sUzIZydskuFiwVh+Zagl6wbAwACaRIkNQR
6yVeoBDmcYAomWXEOSVRDBNviVLGobnWqI1rTfgvf566UhlFRxhp1pIXMOF7TZKPw8OMLEXP/RK8
uhrk+co5YSImYdGrcmJY3EdppFu8/+W7v3/6xvnrt5/fv/k+73QXz3X8EKfR1wSlH+oARrsNw7sf
3v7x+9t3P377569vLP77GZrp8ClJMHce4kvnCUtgcJYR4Fl2PYtpjIhu0U8jjlIke7H4H0H8dPTD
NaLIghtAJHTcswxkxgY8Wb0wCE/ibCWIxeODODGAZ4zRAcusUXgg+9LCPF2lkb3zbKXjniB0Yes7
QKmR59FqCfpKbC6DGBs0H1OUChThFAtHPmPnGFtG95wQI65nJMwYZwvhPCfOABFrSKZkZsymrdF9
kkBe1jaCkG8jNmfPnAGjtlEP8YWJhNWBqIX8FFMjjCdoJVBiczlFCdUDfopEbCM5WWehjhtxAZmO
MGXOaI45t9k8ymC8WtIfgMTY035G14mJzAQ5t/k8RYzpyCE7D2KULG3YCUljHfsFP4cpipzHTNjg
Z8xcIfIe8gDicSjdzwg20n21GjwFddUpbSeIfLLKLLk8wcyYv5M1XSCspAbE39D0hKRXCvyOtPv/
nrSfkTSMmWVEtyXqdtdGRq4p5/2MWNfT/R0RP4Tble6AZXPy6Sv3EK3SxxgWy375+l+4/xdu9z8v
3IfW8+3L9VahQbzl1jXfrKute3Jw574glE7EmuJTrjbvHOrSfAyN0k69t+LyTW4Zw6VcydCBgYsy
pGycjImviIgnMVrCDr/uSicRL1xH3FkyDht/1Wz1LfF0lZyxef7CWq/Ll9NcPDgS2/aaX7bDy4bI
0a329iWsdK/YRupleUNA2l6HhNaZSaJpIdHeNMogqVdzCJqFhBrZrbDoWlh0pPtNqvZYALUyK7Bx
cmC71XN9D0zACN6pEMVzmac81ZvsqmTeZqYPBdOYAbCL2MyAbaa7kuvB4cnR5VPtIzJtkNCmm0lC
RUbVMB4j+CajPqcUKSwWxF6UtzSum+vuNqUGPRmKzWrY0mh3PhSMm+Ya7Ha1gaa6UtDUuey5raYP
UyZEy567gBd/uEyWMHe43PAiGsH3s1Bk+YK/ibIsMy6GiMd5wJXo5GqQEIEzh5Kk58rhl7OBpkpD
FLd6AwThkyXXBVn51MhB0s0k48UCh0JPu9YiI53fgsLnq8D6VJnfHCwt2QrSPYnnl86MrrInCKaY
367LAM4Jh+8/9TyacwIfNEsh286/ncJUyK7+RVHNobwd0WWMioqii3kOV1Je0lF3ZQy0u2LMEFAt
JEUhnEWywOpBNappWTVyDger7tVGMnKaaG5rpqEqsmraxdToYVMGdmJ5syKvsdqEGMqlXuFz6d6V
3O5G63b2CWWVgICX8bNU3Y8oCBq1bWcGNcl4X4alZhetZu3YDPAKah9TJLTi09q43YlbWSOs3UHj
jSo/2O3OWmhabPaVKtLq7EM/nGCzFyAeQ/gMvKKCq1TC0UOGYEM0UdUylw1YIi9FsTTgylllpOe+
qvl9L2j4QaXW8UcVr+nVKh2/36z0fb9ZH/n12nDQeA2FRcRJ3c/PXcbwIYqui9MX1b53ApNsvrXd
CVlSZepkpaqIqxOYesM4gclPU5ypPGBxHQKi86rVGHeb3UGr0m32xxVvOOhUukFrUBm2gvZwPAz8
Tnf82nUuFNjrNwOvNepUWvUgqHitmqTf6VbaXqPR99r9zsjrvy62MTDyXD6KWEB4Fa/jfwAAAP//
AwBQSwMEFAAGAAgAAAAhAA3RkJ+2AAAAGwEAACcAAAB0aGVtZS90aGVtZS9fcmVscy90aGVtZU1h
bmFnZXIueG1sLnJlbHOEj00KwjAUhPeCdwhvb9O6EJEm3YjQrdQDhOQ1DTY/JFHs7Q2uLAguh2G+
mWm7l53JE2My3jFoqhoIOumVcZrBbbjsjkBSFk6J2TtksGCCjm837RVnkUsoTSYkUiguMZhyDidK
k5zQilT5gK44o49W5CKjpkHIu9BI93V9oPGbAXzFJL1iEHvVABmWUJr/s/04GolnLx8WXf5RQXPZ
hQUoosbM4CObqkwEylu6usTfAAAA//8DAFBLAQItABQABgAIAAAAIQDp3g+//wAAABwCAAATAAAA
AAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhAKXWp+fAAAAA
NgEAAAsAAAAAAAAAAAAAAAAAMAEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAGt5lhaDAAAA
igAAABwAAAAAAAAAAAAAAAAAGQIAAHRoZW1lL3RoZW1lL3RoZW1lTWFuYWdlci54bWxQSwECLQAU
AAYACAAAACEAerYtBMQGAACPGgAAFgAAAAAAAAAAAAAAAADWAgAAdGhlbWUvdGhlbWUvdGhlbWUx
LnhtbFBLAQItABQABgAIAAAAIQAN0ZCftgAAABsBAAAnAAAAAAAAAAAAAAAAAM4JAAB0aGVtZS90
aGVtZS9fcmVscy90aGVtZU1hbmFnZXIueG1sLnJlbHNQSwUGAAAAAAUABQBdAQAAyQoAAAAA
------=_NextPart_01D5C645.F27EFFB0
Content-Location: file:///C:/C9124321/file7249_archivos/colorschememapping.xml
Content-Transfer-Encoding: quoted-printable
Content-Type: text/xml