Caminos y circuitos.

Camino.
Es una sucesión de lados que van de un nodo x a un nodo w (dichos lados se pueden repetir).

Circuito o ciclo.
Es un camino del nodo w al nodo w, esto es, un camino que regresa al mismo nodo de donde salió.


Circuito simple de longitud n.
Es aquel camino del nodo w al nodo w que solamente tiene un ciclo en la ruta que sigue.

Camino simple de longitud n.
Es una sucesión de lados que van de un nodo x a un nodo w, en donde los lados que componen dicho camino son distintos e iguales a n. Esto significa que no se puede pasar dos veces por una misma arista.

Camino de Euler.
Es aquel camino que recorre todos los nodos pasando por todas las aristas solamente una vez. Una característica importante de los grafos que tienen camino de Euler es que siempre comienzan y terminan en nodos que terminan en valencia impar.

Circuito de Euler.
Es aquel ciclo que recorre todos los nodos pasando por todos las aristas solamente una vez.
Un grafo tiene un Circuito de Euler si y solo si es conexo y todos sus nodos tienen valencia par.

Algoritmo de Fleury.
Nos permite determinar un circuito de Euler:
1)Verificar que el grafo sea conexo y que todos los nodos tengan valencia par. Si no cumple el grafo no tiene circuito de Euler y finalizar.
2)Si cumple con la condición anterior, seleccionar un nodo arbitrario para iniciar el recorrido.
3)Escoger una arista a partir del nodo actual. Esa arista seleccionada no debe de ser “lado puente”, a menos que no exista otra opción.
4)Desconectar los nodos que están unidos por la arista seleccionada.
5)Si todos los nodos del grafo ya estan desconectados, ya se tiene un circuito de Euler y finalizar. De otra manera continuar con el paso 3.