Definición del problema
Un ciclo hamiltoniano, también llamado circuito de Hamilton, ciclo de Hamilton, es un ciclo de gráfico (es decir, en circuito cerrado) a través de un gráfico de visitas que debe visitar cada nodo exactamente una ves. Por convención, la gráfica trivial en un solo nodo se considera que posee un ciclo de Hamilton, pero el gráfico conectado a dos nodos no lo es. Un gráfico que posee un ciclo hamiltoniano se dice que es un grafo hamiltoniano . El ciclo hamiltoniano es el nombre de Sir William Rowan Hamilton, quien ideó un puzzle en el que este camino a lo largo de los bordes poliedro de un dodecaedro se solicitó (el juego Icosian ).
Un ciclo hamiltoniano de un grafo, que sin embargo, sólo da resultados correctos para los grafos no dirigidos. Del mismo modo, todos los ciclos hamiltonianos de un grafo dado se puede encontrar utilizando el comando HamiltonianCycle [g, todo] en el Mathematica paquete Combinatorica. Tenga en cuenta que estos comandos devolverá el índice del primer punto como el último punto y con el fin de indicar que el resultado es un ciclo cerrado. Una lista de todos los ciclos precalculadas hamiltoniano para muchos gráficos nombre se puede obtener utilizando GraphData gráfico ["HamiltonianCycles"], donde estos ciclos no duplicar el índice de inicio y finalización, y las dos orientaciones de los ciclos se incluyen (de manera que
Un circuito hamiltoniano, o de Hamilton, es un grago G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.
Determinar si un grafo no dirigido dado tiene un ciclo hamiltoniano.
- Aunque el problema es muy parecido al del circuito de Euler, no se conoce ningún algoritmo eficiente para resolverlo, en tiempo polinomial.
- El problema del ciclo hamiltoniano pertenece a un conjunto de problemas de difícil solución llamado problemas NP-completos.
- La solución requiere básicamente evaluar todas las posibilidades, dando lugar a un orden de complejidad exponencial o factorial.
- Otra posibilidad es usar métodos heurísticos, que pueden funcionar en algunos casos y en otros no.
El problema de encontrar un ciclo hamiltoniano es NP- completo por lo que la única manera conocida para determinar si un general grafo tiene un ciclo hamiltoniano es llevar a cabo una búsqueda exhaustiva . Rubin (1974) describe un procedimiento de búsqueda eficiente, que puede encontrar algunas o todas las rutas y circuitos de Hamilton en un grafo con las deducciones que reducen en gran medida marcha atrás y las conjeturas. Un algoritmo probabilístico también puede ser útil para encontrar los ciclos hamiltonianos y caminos.
El análisis asintótico es exponencial ya que no sabemos cuantos pasos hará nuestro algoritmo porque tenemos que visitar cada vértice y también analiza si este ya fue visitado anteriormente y es : (n!
Estructura de Datos utilizadas
En este algoritmo lo que utilice fue grafos ya que contamos con nodos y vértices que son los que unen un determinado grafo en especial los grafos no dirigidos. Y también necesite listas ya que necesitamos punteros para poder ir dirigiéndose de un nodo a otro y así sucesivamente.
Aplicaciones al Ciclo Hamilton
Un problema muy común en el ciclo de Hamilton es el problema del viajero que es de optimización combinatoria. El numero finito (n!), exponencial de ciclos hamiltonianos hace que no podamos verificar si un ciclo hamiltoniano en particular sea minimo en tiempo acotado por un polinomio en n. Es decir que el problema del agente viajero es NP- completo.
Lo que se tiene que realizar en este problema es de que te dan una lista de ciudades y sus costos lo que tenemos que encontrar el recorrido mas corto posible que tiene que visitar todas las ciudades que se dan una sola ves.
Otra de las aplicaciones que tiene el ciclo de hamilton y que presenta este algoritmo es el Juego Icosian.
El juego Icosian, también llamado el juego de Hamilton (Ball y Coxeter 1987, p. 262), es el problema de encontrar un ciclo hamiltoniano en los bordes de un dodecaedro , es decir, un camino de tal manera que cada vértice es visitado una sola vez, no borde es visitado dos veces, y el punto final es el mismo que el punto de partida (a la izquierda la figura). The puzzle was distributed commercially as a pegboard with holes at the nodes of the dodecahedral graph , illustrated above (right figure). 
El puzzle se distribuyó comercialmente como una lámina de cartón con agujeros en los nudos del grafo dodecaedro , que se ilustra arriba (figura de la derecha). The Icosian Game was invented in 1857 by William Rowan Hamilton. Hamilton sold it to a London game dealer in 1859 for 25 pounds, and the game was subsequently marketed in Europe in a number of forms (Gardner 1957). El juego fue inventado Icosian en 1857 por William Rowan Hamilton. Hamilton se lo vendió a un distribuidor de juegos de Londres en 1859 por 25 libras, y el juego fue comercializado posteriormente en Europa en una serie de formas (Gardner 1957).
Ejemplos
Autoevaluación
Yo me siento que si aprendi muchas cosas en este curso que me ayudaron mucho, aunque si me faltaron algunas ya que no las entendi muy bien, como el pseudocodigo entre otras, en general del tema que me toco del proyecto 5 pues a mi si me gusto mucho y si entendi lo que el algoritmo tiene que realizar, y otra cosa que necesito cambiar es no dejar todo para ultima hora si no hacerlo con tiempo y no estar a la carrera el ultimo dia todo estresado y preocupado, también me sirvio mucho este curso para aprender cosas nuevas y aunque varias no las entendi muy bien me sirve mucho para mas adelante en mi carrera, y esto que aprendi pues me ayudara mucho.
Bueno compañeros y maestra este fue mi proyecto 5 si tienen alguna duda o pregunta solo dejen su comentario y yo se las hare saber con mucho gusto.
Bibliografía
