No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Algoritmo de Fleury

37/40
Recursos

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.

Los pasos que seguir son:

  1.    Verificar grado del grafo.
    
  2.    Realizar un circuito cerrado.
    
  3.    En cada nueva iteraci贸n realizar un nuevo camino cerrado visitando aristas que no han sido visitadas.
    
  4.    Reemplazar cada nuevo circuito en el inicial hasta visitar todas las aristas.
    

Aportes 32

Preguntas 1

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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!

Estuvo bastante interesante este curso, aunque cre铆 que m谩s all谩 de los 谩rboles, ciclos y matrices, ver铆amos otros temas de matem谩ticas discretas.

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.