caminos y circuitos

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGÎA

Licenciatura en Informática

Materia:
Matemáticas Discretas.




Tema:
Circuitos y Caminos de Euler
Circuitos y Caminos Hamiltoneanos.















I PARTE
CAMINOS Y CIRCUITOS DE EULER.

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 unasola 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 nodirigido, 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.

Euler demostró que es sencillo determinar si existe un camino de Euler en el grafo, ya quetodo 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.
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 cantidadde 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 quese vayan encontrando, de tal manera de registrar los nodos del camino e imprimir sus enlaces, así como poder verificar caminos alternativos en cada nodo.

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 deadyacencia de cada nodo y la pila P que lleva registro del tour.





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:v1e1 v2 e3 v3 e2 v1



Grafos Eulerianos
Entrada: G = (V, E) conexo con d(v) par para todo v ∈ V. Salida: Un circuito Euleriano de G. Comenzar por cualquier v´ertice v y construir un ciclo Z.

Mientras E \ Z 6= ∅ hacer:
Elegir w tal que exista (w, u) ∈ Z y (w, z) ∈ E \ Z.
Desde w construir un ciclo D con D ∩ Z = ∅.
Z := unir Z y D por medio de w.
Fin mientras
Retornar Z.




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. 
 
Una vez que las listas de adyacencias estén vacías el algoritmo haculminado 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ónganos 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...