CIRCUITOS DE EULER Y HAMILTON
Contenido
Circuitos de Euler ´ Deï¬nicion Algoritmo para determinar circuitos eulerianos
Circuitos de Hamilton
Contenido
Circuitos de Euler ´ Deï¬nicion Algoritmo para determinar circuitos eulerianos
Circuitos de Hamilton
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 ´ Deï¬nicion 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 A± 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 siguientesgrafos tienen circuitos o caminos Eulerianos
? (Nota: VG = VH = VF = ) EF = , , , ,
, , } EG = , , , , , }
EH = , , , , , , , } VI = EI = VJ = EJ =
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 ´ Deï¬nicion Algoritmo para determinar circuitos 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 = 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 ? VG = EG = , , , , } VH =
EH = , , , , , , , , ,
, } VF = EF = , , , , , , , , , , , } ´ R//:
Solo los grafos G y H. Pues solo tienen 2 vertices 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 vertices de grado impar.
2. Ejecutar el algoritmo para determinar el circuito euleriano ( ya existente). 3. Del
circuito euleriano obtenido, eliminar la arista adicionada. 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, 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 = y xi = xj para 0 ≤ i < j ≤
n. Un circuito x0 , x1 , . . . , xn , x0 (con ns1) 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 ? VG = EG = , , , , , , } VH = EH = , , , } VF = EF = , , , , , , }
Circuitos de Hamilton (3)
No se conocen condiciones necesarias y suï¬cientes para la existencia de
circuitos hamiltonianos. Si se conocen teoremas que dan
condicionessuï¬cientes para la existencia de circuitos hamiltonianos.
Hay propiedades para demostrar que un grafo no
contiene ´ un circuito hamiltoniano (ej: grafo con vertice de grado 1). Un
circuito hamiltoniano no puede contener un circuito ˜ ´ mas pequeno dentro de
el. Ideas
´ Ambas aristas de un vertice de grado 2 tienen que formar parte del circuito
hamiltoniano . ´ Al pasar por un vertice pueden
descartarse todas las aristas incidentes con el que no sean las usadas en el
circuito.
Circuitos de Hamilton (4)
Algunas condiciones suï¬cientes para la existencia de circuitos hamiltonianos
son:
Teorema de DIRAC
(Gabriel A. Dirac en 1952) ´ Sea G un grafo simple con n vertices 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 vertices para n ≥ 3
tal que ´ deg(u) + deg(v ) ≥ n para cada par de vertices 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 ´ K3 (grafo completo de 3 vertices) K5 Kn Q2 (2-cubo) Q3 ´ W3
(rueda de 3 vertices) K5
