Algoritmo de Fleury.pptx

Explicación y ejemplo del algoritmo de Fleury en un grafo

1. Algoritmo de Fleury para encontrar un circuito euleriano

2. Circuito de Euler Un circuito de Euler (Euleriano) es un circuito que incluye todos los lados - y por lo tanto todos los vértices - de un grafo dado una y solo una vez.

3. Determinar si tiene circuito de Euler Para determinar si un grafo tiene circuito de Euler, se debe cumplir la condición de que todos sus vértices deben tener grado par . Otra manera de determinar si un grafo tiene circuito de Euler, es si exactamente dos de sus vértices son de grado impar . G(2) G(2) G(2) G(2) G(4) G(4) G(2) G(2) G(3) G(3)

4. Algoritmo de Fleury Es un algoritmo que se utiliza para encontrar un circuito de Euler en un grafo. Los pasos que se siguen en el algoritmo de Fleury son los siguientes: 1) Verificar si existe un circuito de Euler en el grafo. 2) Seleccionar un vértice arbitrario. 3) Elegir una arista, que no sea puente (es decir, que no desconecte del grafo), a partir del vértice. 4) Desconectar los vértices unidos por dicha arista (borrar la arista). 5) Cuando todos los vértices se hayan desconectado, entonces hemos encontrado el circuito de Euler.

5. Ejemplo Tenemos el siguiente grafo:

6. Paso 1 El primer paso es verificar si existe un circuito de Euler con una de las dos formas antes dadas. Del gráfico podemos identificar que: G(V1)=2; G(V2)=4; G(V3)=4; G(V4)=2 y G(V5)=2 Como podemos observar, todos los vértices tienen grado par, lo que indica que sí existe un circuito de Euler.

7. Paso 2 Ya que hemos comprobado la existencia de un circuito de Euler, continuamos con el siguiente paso, Seleccionar un vértice arbitrario: En esta oportunidad vamos a elegir el vértice 4

8. Paso 3 Continuamos con los pasos del algoritmo, ya hemos elegido un vértice por donde empezar, ahora debemos seleccionar una arista que conecte con este vértice y, a su vez, no desconecte del grafo: Podemos ir por la s aristas E4 y E5, ya que ninguna de ellas desconecta del grafo. Optaremos ir por la arista E5 .

9. Paso 4 Ya hemos elegido por que arista ir, por lo que podemos desconectar los vértices que esta unía, es decir, la borramos: Habiendo eliminado la arista que unía los vértices, anotamos aquellos vértices por lo cuales hemos hecho “escala”. V4; V2

10. Desde el punto anterior, ahora solo se repetirá los pasos 3 y 4 hasta que no queden más conexiones: Ahora podemos pasar por E2 y E3, pero por elección propia será E2. Anotamos los vértices por donde pasamos: V4;V2; V1

11. Podemos ir únicamente por E1 Anotamos los vértices: V4;V2;V1; V3

12. Ahora, si observamos, podemos ir por E7, E4 y E3; pero la arista E4 desconecta del grafo, por lo que la descartamos. Decidimos ir por E7 , borramos la arista y anotamos los vértices: V4; V2; V1; V3; V5

13. Desde este punto ya solo existe una arista por donde ir, lo que indica nos aproximamos al paso final del algoritmo. Vamos por E6 Anotamos los vértices: V4; V2; V1 ;V3; V5; V2

14. Continuamos por E3 Anotamos los vértices: V4; V2; V1; V3; V5; V2; V3

15. Finalmente estamos por concluir, solo falta eliminar la última arista que queda.

16. Paso 5 Habiendo eliminado la última arista y anotado el último vértice, hemos encontrado el circuito de Euler y aquellos puntos por los que pasa. Los vértices en que se debe pasar: V4; V2; V1; V3; V5; V2; V3; V4

17. FIN