Algoritmo De Fleury

ALGORITMO DE FLEURY Definición.-

El algoritmo de Fleury permite determinar un circuito de Euler, yun 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.Por lo que definiremos sobre el algoritmo de Fleury que define diferentes autores que se describe en ello.

Según MICHA (2003), en su libro “Matemáticas Discretas” define algoritmode Fleury.Los teoremas de Euler nos proporcionan criterios muy simples para decidir si una grafica posee una trayectoria o un circuito de Euler. Desafortunadamente los teoremas de Euler no nos ayudan a encontrarlos en el caso de que si existan. Ya vimos el caso de graficas sencillas podemos reconstruir lastrayectorias o circuitos de Euler por medio de ensayo y error.Por ejemplo, si nos dan una grafica con solo 6 vértices, todo de grado par, esmuy probable que sea tan fácil construir un circuito de Euler por medio deensayo y error como por medio de la aplicación de un procedimientosistemático. Sin embargo, la mayoría de las graficas que surgen de situacionesprácticas pueden tener cientos o miles de vértices. Para este tipo de graficas esnecesario usar un algoritmo. Ya vimos que en una grafica conexa, un puente es una arista tal al la, la grafica se vuelve disconexa.

El algoritmo de Fleury nos instruye que viajemos por un puente solo comoúltimo recurso. Es decir, solamente podemos usar un puente cuando este seala única arista que se pueda usar para continuar el recorrido. En un lenguajecoloquial podemos resumir la regla fundamental del algoritmo de Fleury en lasiguiente frase:

“No cruces un puente a menos que no te quede otro remedio”

A) El algoritmo de Fleury:

El algoritmo de fleury es un algoritmo que data de 1883, encuentra un tour o camino euleriano en un grafo no dirigido, sabiendo si existen por el siguiente teorema:

Teorema 1

Sea G un grafo no dirigido y conexo:

•G es euleriano si y sólo si no tiene vértices de grado impar.

•G contiene un camino euleriano si y sólo si tiene exactamente dos vértices de grado impar.

Llegamos a la conclusión que el grafo tres es euleriano ahora debemos seguir los siguientes pasos:

Paso 1:

- Creamos una cadena dónde iremos guardando nuestro camino euleriano

T = {}

Paso 2:

•Seleccionamos un vértice x.

•Seleccionamos una arista incidente a x, que no desconecte el grafo si la quitamos.

•Añadimos la arista a nuestra cadena y la quitamos del grafo

•Si x no tiene más aristas incidentes lo quitamos.

T = {e3 }

Repetimos el paso 2

T = {e3 e2}

Como el vértice

...