Circuitos de Euler y Hamilton

Slide 1: 

Estructuras Computacionales Discretas II Comp2502 Prof. E. Maldonado Circuitos: Euleriano y Hamiltoniano

Circuito Euler o Euleriano : 

Circuito Euler o Euleriano Leonard Euler - matemático suizo que resolvió el problema de que una grafo tuviese un solo camino cerrado que contenga a cada una de las aristas. Por lo tanto, el camino cerrado que contiene exactamente cada una de las aristas se conoce como circuito de Euler o euleriano.

Teorema de Euler oCircuito Euleriano : 

Teorema de Euler oCircuito Euleriano Si todos los vértices de una grafo conexo tienen valencia o grado par, entonces el grafo tiene un circuito euleriano. Euler demostró que una grafo que tiene un circuito euleriano tiene valencia par en todos sus vértices. Si exactamente 2 de los vértices son impares ( y el resto es par) entonces es un camino euleriano.

Ejercicios (continuación) : 

Ejercicios (continuación) ¿Qué grafos tienen circuitos eulerianos? Para las que no lo tengan dé una explicación. Para que lo tengan, dé un circuito Euler.

Slide 5: 

Así como el Teorema de Euler indica que las grafos tienen caminos cerrados que usan cada arista exactamente una vez; el algoritmo de FLEURY nos da una manera de construir estos caminos cuando existen. Algoritmo Fleury

Ej. Algoritmo de Fleury : 

Ej. Algoritmo de Fleury

Slide 7: 

Un circuito hamiltoniano es un camino cerrado que utiliza cada vértice del grafo exactamente una vez, exceptuando el último que es igual al primero, o sea vértice inicial = vértice terminal (matemático Sir William Hamilton). Circuito Hamiltoniano

Slide 8: 

Euler postula que en una grafo un camino cerrado puede utilizar cada arista una sola vez. Hamilton postula que en un grafo un camino cerrado puede utilizar cada vértice solo una vez. ¿Pueden existir grafos que contengan un circuito euleriano y uno hamiltoniano? ¿O que solo contengan uno de los dos? Euler vs Hamilton

¿En qué grafos existen circuitos eulerianos y/o hamiltonianos? : 

¿En qué grafos existen circuitos eulerianos y/o hamiltonianos?

Ejercicios : 

Ejercicios

Slide 12: 

Para obtener esta presentación en formato PDF (portable document format) es necesario: Tener el “Acrobat Reader” en su máquina, sino bájelo en www.adobe.com Si ya está instalado en su máquina oprima el “link” “printable version” que está en la parte superior de la presentación.