Tmp_25567 Euler Y Hamilton

Matemáticas Discretas
Este espacio es creado para difundir de una manera didáctica y
agradable la aplicabilidad de las Matemáticas Discretas
Euler y Hamilton

▼

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érticesimpares”.
(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 puederecorrer.
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 hade 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 aristassin 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 unavez. 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óncombinatoria. 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 elproblema del agente viajero es NPcompleto.

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...