CAMINO DE EULER

Dado G(V,E) no orientado y conexo (sin vértices aislados). Un camino de Euler es una trayectoria que contiene todas las aristas de G y recorre cada arista exactamente una vez.

Caminos de Euler:

{a,b,e,d,c,f,g,d,h,h,i,g}

{g,i,h,h,d,g,f,c,d,e,b,a}

Ciclo o circuito de Euler

Es un camino de Euler con la diferencia que empieza y termina en el mismo  vértice es decir es un camino cerrado que recorre cada arista exactamente una vez. El problema de encontrar dichos caminos fue discutido por primera vez por Leonard Euler.

      

Teorema 1. Sea G un grafo o multigrafo no dirigido. Entonces G tiene un ciclo de Euler si, y solo si, es conexo y todo vértice tiene grado par. Diremos que es un grafo Euleriano.

Teorema 2. Sea G un grafo o multigrafo no dirigido. Entonces G tiene un camino de Euler si, y solo si, es conexo y tiene solo dos vértices de grado impar. Diremos que el grafo es semi-Euleriano.

   

EN RESUMEN


Llamamos CAMINO EULERIANO al camino que recorre todas las aristas de un grafo una sola vez, pero que puede pasar por un mismo vértice varias veces. Cuando el camino comienza y termina en el mismo vértice se le denomina CICLO EULERIANO (circuito ó camino cerrado). Si un grafo tiene un camino euleriano, se dice que el grafo es euleriano. 



Existen dos casos de grafos eulerianos, en el primer caso el camino comienza y termina en el mismo vértice formando un Ciclo Euleriano, y en el segundo el camino comienza y termina en distintos vértices formando un Camino Euleriano.



Para que se de el primer caso, que es un Ciclo Euleriano, se han de cumplir las siguientes condiciones:

-El grafo es conexo.
-El grafo es no dirigido.
-Todos los vértices son de grado par.
-Se comienza y se termina en el mismo vértice.



Para el segundo caso, que es un Camino Euleriano (no cerrado), se deben cumplir las siguientes condiciones:

-El grafo es conexo.
-El grafo es no dirigido.
-Exactamente 2 vértices son de grado impar y todos los demás vértices son de grado par.
-Se comienza en uno de los vértices de grado impar y se terminar el camino el otro vértice de grado impar.




Ejemplo de un ciclo de Euler:

Ejemplo de un Camino de Euler:

Ejemplo de un ciclo de Euler

Ejemplo de un grafo que no Euleriano

Dato extra: Los caminos hamiltonianos recorren todos los vértices de un grafo sin pasar dos veces por el mismo vértice, al contrario del camino euleriano que busca recorrer todas las aristas una sola ves pasando varias veces por los mismo vértices.