A√ļn no tienes acceso a esta clase

Crea una cuenta y contin√ļa viendo este curso

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 25

Preguntas 1

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesi√≥n.

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.

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

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.

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.

Fue sorprendente el final, muy interesante

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

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.

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

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.

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

Que buena clase de algoritmos.