Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.
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.
CICLO HAMILTON: Es un ciclo simple que contiene todos los vértices
de G.
Un
ciclo Hamiltoniano es una trayectoria que empieza y termina en el mismo
fuente:http://www.prof2000.pt/users/miguel/grafos/cirham.html
No hay comentarios:
Publicar un comentario