Euler y Hamilton

Ciclo de Euler: Recorre todas las aristas del grafo sin repetir ninguna.

Teorema: Sea G un grafo (finito y conexo).

(a) la suma de las valencias de todos sus vertices es par. Es decir, hay un “número par de vértices impares”.

(b) Si el número de vértices impares es mayor que dos, el grafo no se puede recorrer [sin pasar dos veces por ninguna arista].

(c) Si el número de vértices impares es cero, el grafo se puede recorrer. Podemos además elegir por qué vértice empezar, y el camino siempre será cerrado (termina donde empezó).

(d) Si el número de vértices impares es dos, el grafo se puede recorrer, pero el camino ha de empezar en uno de los dos vértices impares y terminar en el otro.

Matriz para recorrer el grafo sin repetir ningúna arista
Matriz de Euler: A,B,C,D,B,E,D,F,E,C,A
Se recorren todas sus aristas sin repetirlas
Ciclo de Hamilton W.R. Hamilton (1805-1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

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. 

Ciclos de Hamilton
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.