ALGORITMO DE FLEURY
Gracias a los teoremas de Euler es posible
saber si un grafo dado tiene trayectorias o circuitos de Euler, lastimosamente estos teoremas
no indican la manera de encontrar dicho recorrido.
En esta sección se mostrarán una serie de
instrucciones muy sencillas conocidas como El algoritmo de Fleury las cuales
permitirán encontrar una trayectoria o circuito de Euler en caso de que este exista. Una definición
preliminar necesaria es la de puente. Un puente es
Una arista tal que al quitarla grafo se
convierte en un grafo disconexo
El algoritmo
de Fleury (Grafos Eulerianos) que permite encontrar una trayectoria o circuito de Euler.
2 do ejemplo
La gráfica tiene de la figura tiene un circuito de Euler. Sabemos esto porque todo los vértices tiene grado par .aunque esta gráfica es muy simple y podemos encontrar a un circuito de Euler por ensayo y error, lo encontraremos usando el algoritmo de Fleury para entender cómo funciona.
Inicio: Elegimos el vértice F.
Paso 1: Elegimos la arista FC.
Paso 2: Elegimos la arista CD.
Paso 3: Elegimos la arista DA.
Paso 4: Elegimos la arista AC.
Paso 5: Elegimos la arista CE.
Paso 6, 7,8 y 9: Elegimos la arista EA, AB, BD, y DF.
Como ya no podemos seguir, ¡hemos terminado! El circuito de Euler que obtuvimos es: F, C, D, A, C, E, A, B, D, F que es uno de los varios circuitos posibles.
Muy buen ejemplo, pero como se puede hacer evaluando q de la formula de Fleury?
ResponderEliminarEste comentario ha sido eliminado por el autor.
Eliminar