Grafos hamiltoneano y euleriano

CIRCUITOS DE EULER Y HAMILTON
Orlando Arboleda Molina
´ Escuela de Ingenier´a de Sistemas y Computacion de ı La Universidad del Valle

8 de septiembre de 2008

Contenido

Circuitos de Euler ´ Definicion Algoritmo para determinar circuitos eulerianos

Circuitos de Hamilton

Contenido

Circuitos de Euler ´ Definicion Algoritmo para determinar circuitos eulerianos

Circuitos deHamilton

Caminos de Euler

Figura: Ciudad de konigsberg

˜ ´ Resena historica: Los ciudadanos tomaban largas caminatas los domingos. Ellos se preguntaron si era posible iniciar en un sitio, cruzar por todos los puentes una sola vez, y regresar al punto de partida.

Contenido

Circuitos de Euler ´ Definicion Algoritmo para determinar circuitos eulerianos

Circuitos de HamiltonCircuitos de Euler (2)

´ ´ el matematico suizo Leonhard Euler resolvio este problema en ´ 1973 (primera vez en que se utilizo por primera vez la teor´a de ı grafos).

Circuitos y caminos de Euler
Un circuito Euleriano en un grafo G es un circuito simple que contiene cada arista de G. Un camino Euleriano en G es un camino simple que contiene cada arista en G.

Circuitos de Euler (3)

Ejercicio:Cuales de los siguientes grafos tienen circuitos o caminos Eulerianos ? (Nota: VG = VH = VF = {a, b, c, d, e}) EF = {{a, b}, {b, d}, {c, d}, {a, c}, {a, d}, {d, e}, {b, e}} EG = {{a, b}, {b, e}, {a, e}, {e, c}, {c, d}, {d, e}} EH = {{a, b}, {b, e}, {a, e}, {e, c}, {c, d}, {d, e}, {b, c}, {a, d}} VI = {a, b, c, d, e, f , g} EI = {(a, g), (g, c), (c, b), (b, g), (g, e), (e, d), (d, f ), (f , a)} VJ= {a, b, c, d} EJ = {(a, b), (b, c), (c, a), (d, b), (c, d)}

Circuitos de Euler (4)

Teorema 1
Un multigrafo conexo tiene un circuito Euleriano si y solo si ´ cada vertice tiene grado par.

Teorema 2
Un tiene un camino Euleriano pero no un circuito Euler si y solo ´ si tiene exactamente 2 vertices de grado impar.

Contenido

Circuitos de Euler ´ Definicion Algoritmo para determinarcircuitos eulerianos

Circuitos de Hamilton

Circuitos de Euler (5)
´ Algoritmo para la construccion de circuitos eulerianos
Procedimiento Euler ( G: multigrafo conexo con todos los vertices de grado par circuito = circuito en G que comienza en un vertice elegido arbitrariamente H = grafo obtenido al eliminar de G las aristas de circuito Mientras H tiene aristas Inicio subcircuito = uncircuito en H que inicia en un vertice de circuito H = grafo obtenido al eliminar de G las aristas de subcircuito y todos los vertices aislados circuito = circuito con subcircuito insertado en el vertice apropiado Fin ( circuito es un circuito euleriano)

Circuitos de Euler (6)
Ejercicio: Existen circuitos Eulerianos en los siguientes grafos ? VG = {a, b, c, d} EG = {{a, b}, {b, c}, {c, d}, {d, a},{b, d}} VH = {a, b, c, d, e, f , g} EH = {{a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f , g}, {g, a}, {b, g}, {g, c}, {c, f }, {f , d}} VF = {a, b, c, d, e, f , g} EF = {{a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f , a}, {a, g}, {b, g}, {c, g}, {d, g}, {e, g}, {f , g}} ´ R//: Solo los grafos G y H. Pues solo tienen 2 vertices de grado impar.

Circuitos de Euler (7)

Ejercicio: Es posibleadaptar el algoritmo para construccion de circuitos eulerianos, para computar caminos eulerianos ? R//: Sugerencia ´ 1. Adicionar una arista entre los unicos vertices de grado impar. 2. Ejecutar el algoritmo para determinar el circuito euleriano ( ya existente). 3. Del circuito euleriano obtenido, eliminar la arista adicionada. ´ 4. Reconstruir el camino iniciando en uno de los vertices de grado impar.Circuitos de Hamilton

Figura: El juego de la vuelta al mundo de Hamilton

˜ ´ ´ ´ Resena historica: juego inventado por el matematico irlandes William Hamilton. Dado un dodecaedro (poliedro de 12 caras, siendo cada una ´ ´ un pentagono regular) cuyos vertices se marcaron con 20 ciudades del mundo. Es posible iniciar en una ciudad, visitar solo una vez cada una de las otras 19 ciudades,...