Caminos y Paseos de Euler y Hamilton

Caminos y Paseos de Euler y Hamilton

1. Euler

   • Paseo
     • Si una gráfica tiene un paseo euleriano cerrado, entonces todos sus vértices tienen grado par; las aristas donde se empieza y se acaba se pueden aparear para dar ahí el grado par.
     • Siempre deben ser conexo
     • Un camino de Euler es una trayectoria que contiene todas las aristas de G y recorre cada arista exactamente una vez
     • Caminos de Euler: {a,b,e,d,c,f,g,d,h,h,i,g} {g,i,h,h,d,g,f,c,d,e,b,a}
   • Circuitos
     • Un grafo dirigido tiene un paseo de Euler si y solo si es conexo y el grado de entrada de cualquier vértice es igual a su grado de salida con la posible excepción de solo dos vértices.
     • Teroema 1
       • Sea G un grafo o multigrafo no dirigido. Entonces G tiene un ciclo de Euler si, y solo si, es conexo y todo vértice tiene grado par. Diremos que es un grafo Euleriano.
     • Teorema 2
       • Sea G un grafo o multigrafo no dirigido. Entonces G tiene un camino de Euler si, y solo si, es conexo y tiene solo dos vértices de grado impar. Diremos que el grafo es semi-Euleriano.

2. Hamilton

   • Paseos
     • Un ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G.
     • Un pase hamiltoniano es un paseo que lpasa a travez de cada un adde los vertices exactamente una vez
   • Circuitos
     • Un paseo hamiltoniano es un paseo que pasa a través de cada un de los vértices exactamente una vez.
     • Un ciclo hamiltoniano es una trayectoria que empieza y termina en el mismo vértice y pasa por cada vértice una sola vez.
   • El nombre de hamiltoniano se debe a William Rowan Hamilton (1805- 1865). Ideó un puzle que consistía en un dodecaedro con puntas clavadas en sus vértices y cada vértice rotulado con el nombre de una ciudad. Una cuerda iba unida a una de las ciudades. El objetivo era recorrer todos los clavos con la cuerda pasando una sola vez por cada uno de ellos. Para hacer el puzle más interesante, Hamilton indicaba las primeras ciudades del recorrido

Imágenes y archivos del mapa