• Author / Uploaded
• Douglas Alexander Garcia

Citation preview

m
  m      m  
m

m
m    m    
m 
  m m      
     m      m    

 m   m

    !"#$ !%& %'!()(m*!#+,-.-./ 0"'$%$#12$+34+4,.   *0 ()$)$#)5 6!7#!#)!'84++ 



Ú
    El siguiente algoritmo encuentra un tour o camino euleriano en un grafo no dirigido. a. |i el grafo es euleriano, a partir de un vérticecualquiera de G, construiremos una cadenasimple de forma que no se repitan aristas yno se elijan aristas de corte a no ser que nohaya otra alternativa. Al finalizar este proceso,es decir, cuando hayamos agotado todaslas aristas, habremos obtenido un tour euleriano. b. |i el grafo contiene un camino euleriano comenzaremos con un vértice de grado imparsiguiendo el proceso descrito.



 El resto del recorrido es obvio y el recorrido completo es (F, C, D, A, C, E, A, B, D, F)   

 

 
 Ú
 El pseudocódigo del algoritmo de Fleury es el siguiente: Entrada: Un grafo conexo G = (V,E) con, como máximo, dos nodos de grado impar, donde V es el conjunto de nodos y E es el conjunto de aristas. |alida: Una lista P=v0e1v1e2͙eiviei+1͙emvm que representa el camino que incluye cada una de las aristas de E exactamente una vez. Procedimiento: if existe un nodo grado impar v then P = v donde v es un nodo de grado impar de V else P = v donde v es cualquier nodo de V end if n = |E|; i=1 while i