Aplicaciones De Las Matematicas Discretas

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 alnodo 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 laruta 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 eiguales 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 aristassolamente 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 todossus 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 tenganvalencia par. Si no cumple el grafo no tiene circuito de Euler y finalizar.
2) Sí 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ánunidos por la arista seleccionada.
5) Si todos los nodos del grafo ya están desconectados, ya se tiene un circuito de Euler y finalizar. De otra manera continuar con el paso 3