Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Ciclos Hamiltonianos

Los Ciclos Hamiltonianos en Matemática Discreta
by

Franz León

on 25 November 2011

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Ciclos Hamiltonianos

Ciclos Hamiltonianos ¿De dónde viene la idea? Sir William Rowan Hamilton comercializó un juego a mediados del siglo XIX
en la forma de un dodecaedro. Cada esquina tiene el nombre de una ciudad y el problema era comenzar en cualquier ciudad, viajar por las aristas, visitar cada ciudad justo una vez y regresar a la ciudad inicial. El juego de Hamilton se resuelve, si se encuentra un ciclo que contenga
cada vértice justo una vez (excepto por el vértice inicial y final que aparecen dos veces). Intente encontrar una solución. Ésta es la solución. En honor a Hamilton, un ciclo que contiene cada vértice en G justo una vez, excepto por el vértica inicial y final que aparece 2 veces, recibe el nombre de Ciclo Hamiltoniano. Encontrando el Ciclo Hamiltoniano Grafica sin ciclo hamiltoniano ¿Quién Fue Hamilton?
Hamilton (1805 -1865) fue uno de los academicos mas importantes de Irlanda.
Fue profesor de astronomía en la Universidad de Dublin, donde publicó articuilos de fisica y matemáticas. Hamilton es famoso por inventar los cuaterniones, una generalización del sistema de números complejos. Los cuaterniones proporcionaron la inspiración para el desarrollo del álgebra moderna abstracta. Relacionado a esto, Hamilton introdujo el término vector. Es un ciclo hamiltoniano tomando los caminos (a,b,c,d,e,f,g,a) a b c d e f g El susodicho. El problema del agente viajero El problema del agente viajero, se relaciona con el problema de encontrar un ciclo hamiltoniano en una gráfica.
EL problema dice así:
"Dada una gráfica ponderada G, encuentre en G un ciclo de Hamilton con longitud mínima." Se se puensa en los vértices de una gráfica ponderada como ciudades y en los pesos e las aristas cómo distancias, el problema del agente viajero consiste en encontrar una ruta más corta en la que pueda visitar cada ciudad una vez, comenzando y terminando en la misma ciudad. El ciclo C = (a,b,c,d,a) es un ciclo hamiltoniano. Al sustituir cualquiera de las aristas
en C por cualquiera de las aristas con etiqueta 11 aumentaría la longitud de C; entonces
C es un ciclo hamiltoniano de longitud mínima para G.
Éste es un ejemplo de solución para el problema del agente viajero. a b c d
2 3 3 2 11 11 Aunque existen algoritmos para encontrar un ciclo de Euler en un tiempo x para una grafica con n aristas, todos los algoritmos conocidos para encontrar ciclos de Hamilton requieren un tiempo ya sea exponencial o factorial en el peor caso.
Por ésta razón, los métodos que producen ciclos cercanos a la longitud mínima se usan con frecuencia en problemas que piden una solución al problema del agente viajero.
La fama instantánea espera al descubridor de un algoritmo en tiempo polinomial para resolver el problema del Ciclo de Hamilton (o del agente viajero) o de una demostración de que no existe un algoritmo en tiempo polinomial para estos problemas. Teoremas Teorema 1
Sea K un grafo dirigido completo; es decir, K tiene n vértices y para cualquier par de vértices x,y distintos, exactamente una de las aristas ( x,y ) o ( y,x ) está en K. Este grafo (llamado torneo), contiene siemñpre un camino hamiltoniano (dirigido)

Teorema 2
Sea G=(V,E) un grafo sin lazos (bucles), |V|=n>o=2. Si grad(x)+grad(y)>o=n-1 para todos x y que pertenecen a V, x diferente de y. entonces G tiene un camino hamiltoniano.

Teorema 3
Sea G=(V,E) un grafo no dirigido sin lazos (bucles), con |V|=n>o=3. Si grad(x)+grad(y)>o=n para todos los vértices x,y que pertenecen a V no adyacentes, entonces G tiene un ciclo hamiltoniano Códigos Gray y ciclos hamiltonianos en el cubo-n Usando el modelo de anillo usado en la computación en paralelo, que al ser representado en una gráfica
es un ciclo hamiltoniano simple. Pensemos ahora que los vertices representan procesadores. Una arista entre procesadores p y q indica que p y q se pueden comunicar directamente entre sí. Se ve que cada procesador se puede comunicar directamente con exactamente otros 2 procesadores. Los procesadores no adyacentes se comunican enviando mensajes.


Un cubo-n es otro modelo para la computación en paralelo que, al representarse por una gráfica, es un ciclo simple de 2^n vértices cuales tomamos como procesadores, cuando contene un ciclo de Hamilon deb tenerse n>=2 puesto que un cubo-1 no tiene ciclos, y forzosamente los grados de cada uno de los vértices deben ir en una sucesión (s1,s2,...., s2^n) Una sucesión se llama código Gray. Cuando n>=2 un Código Gray corresponde al
ciclo hamiltoniano.
s1, s2, .... , s2^n, s1
Ya que el ciclo va aumentando y al final regresa al punto de partida sin pasar por
ninguno, para n=1 el código Gray 0,1 corresponde a la trayectoria (0,1,0) que no
es un ciclo por que la arista (0,1) se repite.
El código gray ha sido objeto de extensos estudios en otros contextos.
Por ejemplo se han usado códigos Gray al convertir información analógica en digital. El Recorrido del Caballo En ajedrez, el movimiento del caballo, consiste en recorrer dos cuadros en sentido horizontal o vertical
y un cuadro en dirección perpendicular. El recorrido del caballo de un trablero de nxn comienza en algún
cuadro, visita cada cuadro exactamente una vez con movimientos permitidos, y regresa al cuadro inicial.

El problema radica en determinar para qué valores den existe el recorrido del caballo.
Una grafica hamiltoniana se puede usar para modelar dicho problema. Los cuadros del tablero, con color alternado en blanco y negro de la manera usual, son los vértices de la gráfica y hay una arista entre dos vértices si los cuadros correspondientes en el tablero representan un movimiento permitido para el caballo. Se denota la grafica por GKsub(n). Entonces hay un recorrido del caballo en el tablero de nxn sí y solo sí GKsub(n) tiene un ciclo de Hamilton, para ello n debe ser par debido a que un ciclo hamiltoniano debe visitar cada vértice exáctamente una vez, un ciclo hamiltoniano en GKsub(n) debe tener longitud n^2. Entonces, n debe ser par.

En vista de lo anterior el tablero mas pequeño posible que podría tener un recorrido del caballo es de 2X2, pero no tiene un recorrido por que es tan pequeño que el caballo no tendría movimientos permitidos. El siguiente tablero más pequeño ees de 4x4 aunque tampoco el caballo tiene un recorrido suficiente.
Para una gráfica Gksub(6) tiene un ciclo de Hamilton, y para toda n>=6 es posible realizar un camino de camilton para solucionar dicho problema. La demostración construye de manera explícita ciclos de Hamilton para ciertos tableros mas pequeños y después pega los tableros pequeños para obtener ciclos de Hamilton para tableros mas grandes.
Full transcript