• Author / Uploaded
• rafael

Citation preview

Algoritmo de Fleury Heyner Humanez Almanza, Carlos Sáenz Vertel, Rafael González Álvarez Departamento de Ingeniería de Sistemas Universidad de Córdoba Carrera 6 #No. 77-305, Montería, Córdoba

I.

Introducción

Una

de las partes de la teoría de grafos, esta teoría que permite modelar de forma simple cualquier grafo conexo de grado par, ciclo y circuito euleriano; y es por esto que su ámbito de aplicación es muy general y cubre áreas que van desde la misma matemática. En la teoría de grafos y algoritmo de Fleury podemos decir: Si una gráfica "conexa tiene exactamente dos vértices de grado impar, entonces sabemos por" los teoremas de Euler que no tiene un circuito Euler, pero si tiene al menos una trayectoria de Euler que empieza y termina en dichos vértices. El algoritmo de Fleury (Grafos eulerianos) que permite encontrar una "trayectoria o circuito de Euler. Y un puente es una arista tal que, al quitarla del grafo, el grafo se convierte en un grafo disconexo." Y también podemos encontrar una trayectoria de Euler usando una versión modificada del algoritmo de Fleury. Entonces decimos que el Algoritmo de Fleury nos permite construir un camino euleriano en un gráfico de Euler dado combinado ciclos.

II.

Metodología

El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta:

Dado el mapa de Königsberg, con el rio Pregolya dividiendo el plano en cuatro regiones distintas, que están unidas a treves de los puentes ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes recorriendo solo una vez cada uno y regresando al mismo punto de partida? La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes. Sin embargo, Euler en 1736 en su publicación «Solution problematis ad geometriam situs pertinentis» demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes de Königsberg. Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante una línea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite por todas las líneas una única vez, y regrese al mismo punto de partida. Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir ningún punto conectado con un número impar de líneas. En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes (tres de ellos inciden en tres líneas, y el restante incide en cinco), entonces se concluye que es imposible definir un camino con las características buscadas

Paso 2: Elige un vértice inicial (de manera arbitraria). III. Definición: ALGORITMO DE FLEURY: El algoritmo de Fleury permite determinar un circuito de Euler, y un circuito de Euler es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez. Un grafo tiene un circuito de Euler si y solo si es conexo y todos sus vértices tienen valencia par.

Paso 3: en cada paso, recorre cualquier arista disponible eligiendo un puente solo cuando no haya alternativa. Paso 4: Después de recorrer cualquier arista, bórrala y recorre otra arista disponible. Paso 5: cuando ya no puedas seguir el recorrido, para.

Por lo que definiremos sobre el algoritmo de Fleury que define diferentes autores que se describe en ello. Para la existencia de circuitos o trayectorias de Euler, usaremos los teoremas siguientes: Teorema 1: (Existencia de circuitos de Euler). • •

Si un grafo de algún vértice tiene grado impar, entonces no puede tener ningún circuito de Euler. Si todos los vértices de un grafo conexo tienen grado par, entonces hay por lo menos un circuito de Euler.

•

Implementación en un ejemplo

Se tiene el grafo de la Fig.1 NO DIRIGIDO. La gráfica tiene de la figura tiene un circuito de Euler. Sabemos esto porque todo el vértice 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.

Teorema 2: (existencia de trayectorias de Euler). • Si un grafo tiene más de dos vértices de grado impar, entonces no puede tener una trayectoria de Euler. • Si un grafo conexo tiene exactamente dos vértices de grado impar, entonces tiene por lo menos una trayectoria de Euler. (Puente: un puente es una arista tal que al “quitarla” el grafo se convierte disconexo).

Fig. 1

Inicio: Elegimos el vértice F. (Trayectoria: es una trayectoria que recorre todas las aristas de un grafo conexo).

Paso 1: Elegimos la arista FC.

(Circuito: es una trayectoria de Euler, pero además es un circuito que comienza y termina por el mismo vértice). El algoritmo de Fleury nos instruye como regla fundamental, que viajemos por puente solo como último recurso.

Pasos para su ejecución: • • • •

Notación: Aristas Puente Trayectoria y circuito.

Para implementar el algoritmo de Fleury Primero tenemos que seguir unos pasos para encontrar un circuito de Euler. Paso 1: cerciórate que la grafica sea conexa y que todos sus vértices tengan grado par.

Fig. 2

Paso 2: Fig. (3) Elegimos la arista CD

Fig. 3 Fig. 6

Paso 3: Fig. (4) Elegimos la arista DA. Paso 6, 7,8 y 9: Fig. (7) Elegimos la arista EA, AB, BD, y DF.

Fig. 4

Paso 4: Fig. (5) Elegimos la arista AC.

Fig. 7

Como ya no podemos seguir, ¡hemos terminado! El circuito de Euler que obtuvimos es: C ={(F, C),(C, D),(D, A),(A, C),(C, E),(E, A),(A, B),(B, D),(D, F)} que es uno de los varios circuitos posibles

IV. Conclusiones El algoritmo de Fleury es útil al momento de encontrar las trayectorias y circuitos de Euler con los diferentes teoremas y pasos para la mayor comprensión del tema. Fig. 5

V. Referencias Paso 5: Fig. (6) Elegimos la arista CE.

[1]. http://caminoseuler.blogspot.com/p/algoritmoleury.html