Algoritmo de Fleury

PLatzi esta encontra de las clases en pizarra , al extremo de no darle plumones o marcadores nuevos

Algoritmo de fleury: Nos ayuda a encontrar un ciclo euleriano.

• 1: verificar el grado de cada vértice para comprobar que todos sean pares.
• 2: Crear un circuito cerrado, no importa que no pase por todas las conexiones.
• 3: En cada iteración crearemos circuitos cerrados con conexiones que no hayan sido visitadas.
• 4: reemplazar cada nuevo circuito en el anterior, hasta visitar todas las aristas.
• 5: Los vértices solo deben aparecer la mitad de su grado veces en la expresión del ciclo.

Apuntes de clase:
El algoritmo de Fleury nos ayuda a encontrar un ciclo eureliano.
Recuerda que un ciclo eureliano tiene que tener sus vértices con grado par, empezar y acabar en el mismo vértice y recorrer una sola vez sus conexiones.

Explicación del algoritmo:

• Tenemos que realizar circuitos o ciclos cerrados con nuestros vertices.
• Una vez tenemos el primer ciclo, realizamos el segundo con conexiones que no tenga el primero.
• Después juntamos los dos ciclos a través del vértice que tenga en común.
• Así hasta haber recorrido todas las conexiones sin repetirlas a través de ciclos cerrados.
• Cuando juntemos los ciclos que hemos obtenidos lo haremos con los vértices que compartan los ciclos.
• Para comprobar si lo hemos hecho bien, los vértices tienen que aparecer la mitad de las veces que el grado de ese mismo vértice tiene, si por ejemplo f tiene grado 4 pues debemos checar que solo haya aparecido 2 veces. si tuviera grado 2 pues solo debe aparecer 1 vez.
  solo el nodo inicial va aparecer 2 veces y será al principio y al final.

Profesor: Un favor, habría la posibilidad de tener los plumones con colores mas resaltantes, en el momento que Ud. explica y utiliza los colores, exceptuando el rojo, no se notan mucho. Es una sugerencia. Saludos

Notas de clase:

• El algoritmo de Fleury va a encontrar un ciclo euleriano.

• Recordemos que un ciclo euleriano es un ciclo donde inicias y terminas en el mismo punto, pasando por todas las aristas una sola vez.

• Pasos del algoritmo:

1. Verificar grado de mi grafo.
2. Realizar un circuito cerrado
3. En cada iteración construye un nuevo camino cerrado visitando aristas incidentes que no han sido visitadas.
4. Reemplazar cada nuevo circuito en el inicial hasta visitar todas las aristas.

Aquí tomé otros ciclos. Los numeros en las aristas indican el camino recorrido para completar el ciclo.

Algoritmo de Fleury
Permite hallar un ciclo Euleriano en el grafo (si lo hubiera)
Pasos

• Verificar los grados de los nodos (todos pares)
• Hallar un ciclo, tratando que no interfiera con el acceso a otras aristas (recuerda que solo se puede pasar por una arista una sola vez)
• Hallar otro ciclo con un vértice de coincidencia que no incluya a las aristas del anterior
• Incorporar ambos ciclos en la arista que tienen en común Ejemplo sean los ciclos: afgba y gedcg el vertice en cumún es g entonces: afgedcgba
• Iterar hasta incorporar todos las aristas

Fue sorprendente el final, muy interesante

Que buena clase de algoritmos.

Este algoritmo si me costo entenderlo, pero finalmene lo hice

El que cada nodo aparezca la mitad de veces que se grado tiene total sentido en verdad.

Si entramos en un nodo, como queremos un ciclo euleriano, no podremos salir por el mismo enlace por el que entramos, por lo que la única forma de salir será usar otro enlace. Es decir, cada nodo que pisemos corresponderá a 2 enlaces, o lo que es lo mismo, las veces que aparezca un nodo serán la mitad de los enlaces que tenga éste (o sea, su grado).

Que buen algoritmo!

Que pasa si un nodo tiene grado 3 porque el ciclo euleriano permite hasta 2 nodos impares no? , tendria que aparecer 1 vez o 2 veces a la hora de fijarnos en si cumple la condición?

El algoritmo de Fleury incia: Verificamos los grados de las aristas en el Grafo, 2. Realizamos un circuito cerrado sin importar si incluye o no a todos los nodos, 3. En cada iteración construye un nuevo camino cerrado visitando las aristas incidentes que no han sido visitadas, 4. Reemplaza cada nuevo circuito en el inical hasta visitar todas las aristas y luego fin.

El objetivo del algoritmo de Fleury, es encontrar un ciclo Eureliano.

Condición de aparición de nodos vs grado dentro del ciclo euleriano

Demostración

Ejercicio práctico sobre Algoritmo de Fleury

Conclusión: TODOS LOS CAMINOS RECORRIDOS UNA VEZ

Encuentra un ciclo Eureliano. Primero encontrar un circuito cerrado. encontrar un segundo ciclo que este incluido dentro del primero, con arista que no halla incluido en el primero

Este algoritmo es genial!!!

Muy buena clase

En estos algoritmos vemos como se relacionan con los ciclos vistos al inicio

Super interesante este algoritmo

Excelente

Curioso.