Page 1 1 Find a maximum flow Value of flow: a s d b e g h t 5 20 20 20 30 5 5 5 20 5 20 20 5 20 30 c f i 25 20 5 10 20 5 20 10 5 Construct a maximum flow and indicate the flow value Find two augmenting paths 2/5 s t 0/1 3/4 3/3 2/4 1/3 3/3 2/2 3/4 1/3 3/3 2/2 3/3 1/3 3/3 1/3 1/3 2/2 1/3 Page 2 1 Find a maximum flow Value of flow: a s d b e g h t 5 20 20 20 30 5 5 5 20 5 20 20 5 20 30 c f i 25 20 5 10 20 5 20 10 5 Construct a maximum flow and indicate the flow value Find two augmenting paths 2/5 s t 0/1 3/4 3/3 2/4 1/3 3/3 2/2 3/4 1/3 3/3 2/2 3/3 1/3 3/3 1/3 1/3 2/2 1/3 2 Build the residual graph d g 3/5 2/4 3/3 s e h t 3/3 1/5 1/5 1/1 1/1 2/5 Residual graph: s d e g h t Proof • Add b units of flow along the path P • What do we need to verify to show we have a valid flow after we do this? – –Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!