CIRCUITO DE EULER

ALGORITMOS DE GRAFOS PARA CAMINOS DE EULER

En la teoría de grafos , un camino euleriano es un camino en un gráfico que visita cada borde exactamente una vez. Del mismo modo, un circuito euleriano o ciclo euleriano es un camino euleriano que comienza y termina en el mismo vértice. Euler demostró que una condición necesaria para la existencia de circuitos de Euler es que todos los vértices de la gráfica tiene una aún grado , y afirmó sin pruebas que los gráficos relacionados con todos los vértices de grado par tiene un circuito euleriano.

Euler demostró que es sencillo determinar si existe un camino de Euler en el grafo, ya que todo lo que hay que hacer es verificar el grado de los nodos. Existen un teorema de la teoría de grafos que establece que un grafo tiene un camino de Euler si y solo sí es este es conexo y exactamente dos de sus nodos tienen grado impar. De manera similar, un grafo tiene un tour de Euler si y solo sí es conexo y todos sus nodos tienen grado par.

Basado en estos teoremas se puede verificar la existencia de un camino de Euler antes de intentar encontrar el camino, lo cual podría ahorrar una gran cantidad de procesamiento en la búsqueda de un camino que nunca logrará encontrarse. Además, la comprobación de grado de los nodos de un grafo es una tarea que fácilmente podría ser de complejidad lineal en el número de nodos del mismo.

Una técnica más adecuada es la de encontrar ciclos en el grafo, borrando de las listas de adyacencia las aristas que se encuentren y almacenando en un pila los nodos que se vayan encontrando, de tal manera de registrar los nodos del camino e imprimir sus enlaces, así como poder verificar caminos alternativos en cada nodo. Esta técnica puede encontrar un tour de Euler, si existe en el grafo, en tiempo lineal.

El siguiente ejemplo ilustra el funcionamiento de esta estrategia sobre un grafo de ejemplo. La secuencia de ilustraciones va de izquierda a derecha y de arriba hacia abajo. En cada una de las figuras podemos ver el grafo, las lista de adyacencia de cada nodo y la pila P que lleva registro del tour. El tour comienza en el nodo 0 y la primera arista a visitar es la 0-1. Nótemos que en la primera figura P dicha arista no aparece en las listas y que en P ya se encuentran los nodos 0 y 1.

Una vez que las listas de adyacencias estén vacías el algoritmo ha culminado su ejecución. La secuencia de nodos que se desapilan de P nos indican un tour de Euler posible para el grafo anterior: 0-6-4-3-2-4-5-0-2-1-0.

Ahora bien, supóngamos que en la sexta imagen no se hubiese viajado al nodo 2 sino al nodo 6, entonces en la séptima figura se hubiese viajado al nodo 0 y desde este último no podemos elegir más enlaces, lo mismo ocurre con el nodo 6. En estos casos el algoritmo desapila de P los nodos aislados y continua con el nodo 4, en cuyo caso el algoritmo culminaría cuando P contenga los identificadores: 0 1 2 0 5 4 3 2 4. Es evidente que desde 4 se puede alcanzar a 6 y a 0 porque estaban apilados luego de él en la pila, así que basta con apilarlos de nuevo en el orden en que apilados originalmente: 6 0. En esta variante del problema se obtendría un tour de Euler diferente al anterior: 0-6-4-2-3-4-5-0-2-1-0. 

 

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. El matemático suizo Leonhard Euler resolvió este problema en 1973 (primera vez en que se utilizo la teoría de grafos).

Definición:

Un camino de Euler en un grafo no dirigido es un camino que usa cada arista exactamente una vez. Si tal camino existe, el gráfico se llama transitable o semi-euleriano.

Un ciclo euleriano o circuito euleriano en un grafo no dirigido, es un ciclo que utiliza cada arista exactamente una vez. Si este ciclo existe, el gráfico se llama unicursal. Si bien los gráficos son gráficos eulerianos, no todo grafo euleriano tiene un ciclo Euleriano. Para grafos dirigidos la ruta tiene que ser sustituida por camino dirigido con ciclo dirigido.

Ejemplos de GRAFO EULERIANO:
Grafo A

 
Grafo Euleriano: No

Tour: v1 e1 v2 e2 v3 e3 v4 e4 v2 e1 v1

Tour Euleriano: No tiene, porque tiene vértices de grado impar

Camino Euleriano: v1 e1 v2 e2 v3 e3 v4 e4 v2



 

Grafo B

Grafo Euleriano: Si


Tour: v2 e1 v1 e2 v3 e3 v2

Tour Euleriano: v1 e1 v2 e3 v3 e2 v1

Camino Euleriano:v1 e1 v2 e3 v3 e2 v1

Propiedades:

* Sea G un grafo no dirigido y conexo:

- G es euleriano si y sólo si no tiene vértices de grado impar.

- G contiene un camino euleriano si y sólo si tiene exactamente dos vértices de grado impar.

* Sea G un grafo dirigido y débilmente conexo:

- Si y sólo si para todo vértice su grado de entrada es igual a su grado de salida.