Ejercicios de FluJo Maximo

7/26/2019 Ejercicios de FluJo Maximo

1/12

ESTRUCTURAS DISCRETAS II

ALUMNA: Paula Del Carpio Bernedo

GRUPO: 01

SEMESTRE:III

LABORATORIO 09

ACTIIDADES

1. Implementar en Python el siguiente cdigo correspondiente al modelo deredes implementado a continuacin:

class FlowNetwork(object:

de! ""init""(sel!:

sel!.adj # $%

sel!.&ow # $%

de! add"'erte(sel!) 'erte:

sel!.adj*'erte+ # *+

de! get"edges(sel!) ':

return sel!.adj*'+

de! add"edge(sel!) u) ') w#,:

i! u ## ':

raise -aluerror(/u ## '/

edge # dge(u)')w

redge # dge(')u),

edge.redge # redge

redge.redge # edge

sel!.adj*u+.append(edge

sel!.adj*'+.append(redge

sel!.&ow*edge+ # ,

sel!.&ow*redge+ # ,


2/12

de! 0nd"path(sel!) source) sink) path:

i! source ## sink:

return path

!or edge in sel!.get"edges(source:

residual # edge.capacity sel!.&ow*edge+

i! residual 2 , and edge not in path:

result # sel!.0nd"path( edge.sink) sink) path 3 *edge+

i! result 4# None:

return result

de! ma"&ow(sel!) source) sink:

path # sel!.0nd"path(source) sink) *+

while path 4# None:

residuals # *edge.capacity sel!.&ow*edge+ !or edge in path+

&ow # min(residuals

!or edge in path:

sel!.&ow*edge+ 3# &ow

sel!.&ow*edge.redge+ # &ow

path # sel!.0nd"path(source) sink) *+

return sum(sel!.&ow*edge+ !or edge in sel!.get"edges(source

g # FlowNetwork(*g.add"'erte(' !or ' in /sop5rt/+g.add"edge(6s6)6o6)7g.add"edge(6s6)6p6)7g.add"edge(6o6)6p6)8g.add"edge(6o6)656)7g.add"edge(6p6)6r6)8g.add"edge(6r6)6t6)7g.add"edge(656)6r6)9g.add"edge(656)6t6)8print (g.ma"&ow(6s6)6t6


3/12

8. Probarlo cambiando los datos y obteniendo el &ujo mimo de los nue'osmodelos de redes

g # FlowNetwork(

*g.add"'erte(' !or ' in /;F/+

g.add"edge(6;6)66)6F6)@

g.add"edge(66)6F6)8

print (g.ma"&ow(6;6)6F6

g # FlowNetwork(

*g.add"'erte(' !or ' in /;F/+

g.add"edge(6;6)6


4/12

g.add"edge(6;6)6>6)@

g.add"edge(66)66)@

g.add"edge(66)6F6)18

print (g.ma"&ow(6;6)6F6

g # FlowNetwork(

*g.add"'erte(' !or ' in /;/+

g.add"edge(6;6)66)6=6)1,

g.add"edge(6>6)6


5/12

1. ntender el cdigo) hacerle un seguimiento y probarlo con lossiguientes modelos de redes:

g # FlowNetwork(*g.add"'erte(' !or ' in /,;F/+g.add"edge(6,6)6;6)Ag.add"edge(6,6)66)7g.add"edge(6;6)66)1g.add"edge(66)6F6)?print (g.ma"&ow(6,6)6F6


6/12

g # FlowNetwork(*g.add"'erte(' !or ' in /sabcdt/+g.add"edge(6s6)6a6)@g.add"edge(6s6)6c6)9g.add"edge(6a6)6b6)8

g.add"edge(6b6)6t6)9g.add"edge(6c6)6a6)1g.add"edge(6c6)6b6)9g.add"edge(6c6)6d6)7g.add"edge(6d6)6b6)7g.add"edge(6d6)6t6)8print (g.ma"&ow(6s6)6t6

g # FlowNetwork(*g.add"'erte(' !or ' in /sabcde!t/+g.add"edge(6s6)6a6)@g.add"edge(6s6)6c6)Bg.add"edge(6a6)6b6)7g.add"edge(6a6)6d6)8g.add"edge(6b6)6e6)7g.add"edge(6b6)6!6)8g.add"edge(6c6)6b6)7


7/12

g.add"edge(6c6)6e6)7g.add"edge(6c6)6d6)7g.add"edge(6d6)6b6)@g.add"edge(6d6)6!6)9g.add"edge(6e6)6t6)?g.add"edge(6!6)6t6)B

print (g.ma"&ow(6s6)6t6

g # FlowNetwork(*g.add"'erte(' !or ' in /;F/+g.add"edge(6;6)66)6=6)@g.add"edge(6>6)66)1g.add"edge(6>6)6F6)9g.add"edge(66)6=6)1g.add"edge(66)6F6)8print (g.ma"&ow(6;6)6F6


8/12

g # FlowNetwork(*g.add"'erte(' !or ' in /1879@?B/+g.add"edge(616)686)Bg.add"edge(616)676)9g.add"edge(616)696)Ag.add"edge(686)696)Bg.add"edge(686)6@6)8g.add"edge(676)6@6)Cg.add"edge(676)6?6)@g.add"edge(696)6@6)Cg.add"edge(6@6)6?6)Ag.add"edge(6@6)6B6)?g.add"edge(6?6)6B6)Aprint (g.ma"&ow(616)6B6


9/12

g # FlowNetwork(*g.add"'erte(' !or ' in /,;F/+g.add"edge(6,6)6;6)Ag.add"edge(6,6)6


10/12

8. Intentar implementar otro ;lgoritmo de Flujo mimo en Pythondi!erente al 'isto en esta clase. =ompararlo y describir sus 'entajas ydes'entajas con respecto al 'isto en clases.

de! FlujoDaimo(!uente)sumidero:

s#!uente

t#sumidero

!#,

while(Erue:

#depth"0rst(s)INE"D;

i! ##,:

break

!#!3

return !

de! depth"0rst(G) r:

de! 'isit(G) -) :

padre # dict(*+

-p # $-%

w # -

while Erue:

i! G*w+4#None:

- # G*w+*,+

n#,

while - in -p and nHlen(G*w+:

- # G*w+*n+

n#n31

i! n##len(G*w+ and - in -p:

- # padre*w+

else:

padre*-+ # w

-p # -p $-%


11/12

E*-+ # *w+

E*w+ # E*w+ 3 *-+

i! len(-p##len(G:

return

w # - E # $r: *+%

'isit(G) r) E

return E

Ja di!erencia de este algoritmo con el implementado en clase es la

e0ciencia de cada uno de ellos) por la utiliKacin yLo reutiliKacin delcdigo) la manera de abstraer e implementar el gra!o y el uso dedi!erentes mMtodos para hallar el &ujo mimo de estos.

-NE;;O:

ste algoritmo para encontrar el &ujo mimo no necesita laimplementacin de clases.

sa una bQs5ueda a pro!undidad 5ue lo 'uel'e ms e0ciente. Ou implementacin no es tan compleja por5ue solo se usan

!unciones.

>O-NE;;O:

Ou tiempo de ejecucin es algo ine0ciente por5ue podrRa llegar atener un orden de n cuadrtico o cubico.

sa 'arias !unciones) en las 5ue el enlaKado puede tener erroresen algunos casos.

CUESTIONARIO

1. S=mo son los algoritmos de Flujo Dimo en los Dodelos de redesT

stos algoritmos buscan el &ujo mimo de un gra!o ponderado dirigidorecorriendo todo el gra!o) nodo por nodo) y comparando las aristas)asignndoles 'alores nulos al principio y despuMs de comparar todas lasaristas y sus pesos de nodo a nodo) se asigna el &ujo 5ue lecorresponde) imprimiendo al 0nal el total de comparaciones 5ue hiKo)siendo el &ujo mimo de la red.


12/12

8. S=untas implementaciones has encontrado del algoritmo de &ujomimo en pythonT >escribe sus di!erencias

Oe encontr un algoritmo 5ue utiliKaba una bQs5ueda a pro!undidad pararecorrer los nodos y saber cual tiene un mRnimo peso) y otro 5ueimplementaba y usaba una bQs5ueda a lo ancho) el uso de estosmMtodos es e0ciente y ahorra muchos recursos en el momento de hallar

el &ujo mimo.; di!erencia de otro algoritmo el cual utiliKaba la iterati'idad para poderrecorrer todo el gra!o representando la red de &ujos) este algoritmo si ese0caK) pero no se ahorra tantos recursos como el tiempo ya 5ue re5uerRade un tiempo de ejecucin cubico) el cual no es e0ciente.

7. S=ul es tu opinin sobre la importancia del algoritmo de FlujomimoT

Ja implementacin y el conocimiento de este algoritmo es muyimportante y de mucha utilidad) por5ue se puede usar para di'ersos

problemas y situaciones en las 5ue se re5uiere saber el &ujo mimo dealguna red) como en una ciudad) cuanto es el mimo de tiempo 5ue sere5uiere de un punto a otro) o la distancia mima 5ue se recorrerRa deun punto a otro) y asR como para alguna carretera) el algoritmo de &ujomimo se puede utiliKar para otros problemas semejantes.

Documents

Ejercicios de FluJo Maximo