Algoritmo De Fleury
Páginas: 3 (606 palabras)
Publicado: 13 de octubre de 2011
REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL DE LA FUERZA ARMADA NACIONAL
NÚCLEO CORO - EXTENSION PUNTO FIJO
Mavo, YoselinC.I: 17.499.673
Chirinos, Alberto C.I: 19.823.052
Ing. Sistemas “B” Nocturno
ALGORITMO DE FLEURY
* Para hallar un circuito Euleriano en un grafo simple G=(V,E) Euleriano):
Comenzamos deun vértice cualquiera v, elegimos una arista e1={v,u}, entonces formamos la cadena v,u. Ahora estamos en u, elegimos una arista e2={u,w} y formamos la cadena v,u,w y asi sucesivamente.
Para que lacadena obtenida al final del proceso sea Euleriana en cada paso i
debemos elegir para continuar la cadena, una nueva arista ei tal que si quitamos esta arista en el grafo G[ E-{e1, ...., ei-1}] seobtenga un grafo conexo.
PSEUDOCÓDIGO DEL ALGORITMO DE FLEURY
El pseudocódigo del algoritmo de Fleury es el siguiente:
Entrada:
Un grafo conexo G = (V,E) con, como máximo, dos nodos de gradoimpar, donde V es el conjunto de nodos y E es el conjunto de aristas.
Salida:
Una lista P=v0e1v1e2…eiviei+1…emvm que representa el camino que incluye cada una de las aristas de E exactamente unavez.
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 <= n do:
E' = {e pertenece a E y e es incidente en v}
e' = cualquier arista de E'
while e' es puente y |E'| > 1 do:
E' = E' - {e'}
e' = (z,w) cualquier arista de Ev
end while
P = P e' w; E = E - {e'}; v =w; i = i +1
endwhile
return P
* APLICACIÓN TEOREMA DE FLEURY
En una empresa de construcciones trabajan 10 empleados, cada uno de ellos está
capacitado para realizar determinadostrabajos, por ejemplo: preparar mezcla, acarrear baldes, levantar paredes, colocar pisos, pintar, etc. Al comenzar cada día de trabajo se hace una lista de tareas a realizar (que pueden ser hechas por un...
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL DE LA FUERZA ARMADA NACIONAL
NÚCLEO CORO - EXTENSION PUNTO FIJO
Mavo, YoselinC.I: 17.499.673
Chirinos, Alberto C.I: 19.823.052
Ing. Sistemas “B” Nocturno
ALGORITMO DE FLEURY
* Para hallar un circuito Euleriano en un grafo simple G=(V,E) Euleriano):
Comenzamos deun vértice cualquiera v, elegimos una arista e1={v,u}, entonces formamos la cadena v,u. Ahora estamos en u, elegimos una arista e2={u,w} y formamos la cadena v,u,w y asi sucesivamente.
Para que lacadena obtenida al final del proceso sea Euleriana en cada paso i
debemos elegir para continuar la cadena, una nueva arista ei tal que si quitamos esta arista en el grafo G[ E-{e1, ...., ei-1}] seobtenga un grafo conexo.
PSEUDOCÓDIGO DEL ALGORITMO DE FLEURY
El pseudocódigo del algoritmo de Fleury es el siguiente:
Entrada:
Un grafo conexo G = (V,E) con, como máximo, dos nodos de gradoimpar, donde V es el conjunto de nodos y E es el conjunto de aristas.
Salida:
Una lista P=v0e1v1e2…eiviei+1…emvm que representa el camino que incluye cada una de las aristas de E exactamente unavez.
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 <= n do:
E' = {e pertenece a E y e es incidente en v}
e' = cualquier arista de E'
while e' es puente y |E'| > 1 do:
E' = E' - {e'}
e' = (z,w) cualquier arista de Ev
end while
P = P e' w; E = E - {e'}; v =w; i = i +1
endwhile
return P
* APLICACIÓN TEOREMA DE FLEURY
En una empresa de construcciones trabajan 10 empleados, cada uno de ellos está
capacitado para realizar determinadostrabajos, por ejemplo: preparar mezcla, acarrear baldes, levantar paredes, colocar pisos, pintar, etc. Al comenzar cada día de trabajo se hace una lista de tareas a realizar (que pueden ser hechas por un...
Leer documento completo
Regístrate para leer el documento completo.