CIRCUITOS DE EULER Y HAMILTON
Orlando Arboleda Molina
Escuela de Ingenierı́a de Sistemas y Computación de
La Universidad del Valle
8 de septiembre de 2008
Contenido
Circuitos de Euler
Definición
Algoritmo para determinar circuitos eulerianos
Circuitos de Hamilton
Contenido
Circuitos de Euler
Definición
Algoritmo para determinar circuitos eulerianos
Circuitos de Hamilton
Caminos de Euler
Figura: Ciudad de konigsberg
Reseña histórica: 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
Definición
Algoritmo para determinar circuitos eulerianos
Circuitos de Hamilton
Circuitos de Euler (2)
el matemático suizo Leonhard Euler resolvió este problema en
1973 (primera vez en que se utilizó 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})
I EF = {{a, b}, {b, d}, {c, d}, {a, c}, {a, d}, {d, e}, {b, e}}
I EG = {{a, b}, {b, e}, {a, e}, {e, c}, {c, d}, {d, e}}
I EH =
{{a, b}, {b, e}, {a, e}, {e, c}, {c, d}, {d, e}, {b, c}, {a, d}}
I 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)}
I 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 vértice tiene grado par.
Teorema 2
Un tiene un camino Euleriano pero no un circuito Euler si y solo
si tiene exactamente 2 vértices de grado impar.
Contenido
Circuitos de Euler
Definición
Algoritmo para determinar circuitos eulerianos
Circuitos de Hamilton
Circuitos de Euler (5)
Algoritmo para la construcción 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 = un circuito 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 ?
I VG = {a, b, c, d}
EG = {{a, b}, {b, c}, {c, d}, {d, a}, {b, d}}
I 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}}
I 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 vértices de grado
impar.
Circuitos de Euler (7)
Ejercicio: Es posible adaptar el algoritmo para construccion de
circuitos eulerianos, para computar caminos eulerianos ?
R//: Sugerencia
1. Adicionar una arista entre los unicos vértices 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 vértices de
grado impar.
Circuitos de Hamilton
Figura: El juego de la vuelta al mundo de Hamilton
Reseña histórica: juego inventado por el matemático irlandés
William Hamilton.
Dado un dodecaedro (poliedro de 12 caras, siendo cada una
un pentágono regular) cuyos vértices se marcaron con 20
ciudades del mundo.
Es posible iniciar en una ciudad, visitar solo una vez cada una
de las otras 19 ciudades, y regresar a la ciudad de origen ?
Circuitos de Hamilton (2)
circuito y camino de Hamilton
Un camino x0 , x1 , . . . , xn en el grafo G = (V , E) es llamado un
camino Hamiltoniano si V = {x0 , x1 , . . . , xn } y xi 6= xj para
0 ≤ i < j ≤ n.
Un circuito x0 , x1 , . . . , xn , x0 (con n¿1) en un grafo G = (V , E)
es llamado un circuito Hamiltoniano si x0 , x1 , . . . , xn es un
camino Hamiltoniano.
Ejercicio: Cuales de los siguientes grafos G, H, F tienen
circuitos o caminos Hamiltonianos ?
I VG = {a, b, c, d, e}
EG = {{a, b}, {b, c}, {c, d}, {d, e}, {e, a}, {a, c}, {b, e}}
I VH = {a, b, c, d} EH = {{a, b}, {b, c}, {c, d}, {d, b}}
I VF = {a, b, c, d, e, f , g}
EF = {{a, b}, {b, g}, {g, e}, {e, f }, {e, c}, {c, d}, {b, c}}
Circuitos de Hamilton (3)
I No se conocen condiciones necesarias y suficientes para
la existencia de circuitos hamiltonianos.
I Si se conocen teoremas que dan condiciones suficientes
para la existencia de circuitos hamiltonianos.
I Hay propiedades para demostrar que un grafo no contiene
un circuito hamiltoniano (ej: grafo con vértice de grado 1).
I Un circuito hamiltoniano no puede contener un circuito
mas pequeño dentro de él.
I Ideas:
I Ambas aristas de un vértice de grado 2 tienen que formar
parte del circuito hamiltoniano .
I Al pasar por un vértice pueden descartarse todas las
aristas incidentes con el que no sean las usadas en el
circuito.
Circuitos de Hamilton (4)
Algunas condiciones suficientes para la existencia de circuitos
hamiltonianos son:
Teorema de DIRAC
(Gabriel A. Dirac en 1952)
Sea G un grafo simple con n vértices con n ≥ 3 tal que todos
los vertices de G tienen grado mayor o igual que n/2.
Entonces, G contiene un circuito hamiltoniano.
Teorema de ORE
(Oystein Ore en 1960)
Sea G un grafo simple con n vértices para n ≥ 3 tal que
deg(u) + deg(v ) ≥ n para cada par de vértices no adyacentes
u y v de G. Entonces, G contiene un circuito hamiltoniano.
Circuitos de Hamilton (5)
Ejercicio: Determinar si los siguientes grafos contienen
circuitos hamiltonianos
I K3 (grafo completo de 3 vértices)
I K5
I Kn
I Q2 (2-cubo)
I Q3
I W3 (rueda de 3 vértices)
I K5
