Consultar ensayos de calidad


Circuitos de euler y hamilton



CIRCUITOS DE EULER Y HAMILTON


Contenido

Circuitos de Euler ´ Definicion Algoritmo para determinar circuitos eulerianos

Circuitos de Hamilton


Contenido

Circuitos de Euler ´ Definicion 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 ´ 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 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 ´ Definicion 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 suficientes para la existencia de circuitos hamiltonianos. Si se conocen teoremas que dan condicionessuficientes 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 suficientes 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







Política de privacidad