Netowrk Flows

Question 1

Question says explain why flow out of F cannot be max capacity how ti answe?

Answer 1

For these always check if max flow in (even if this can’t be achieved) can equal max Flow out

We see max flow in is 90 and max flow out is 95
As ALL THE FLOW MUST GO THROUGH THOSE TWO ARCS, they can never be full capacity as max flow in = max flow out
(This bevause third path had so 0 capacity so can ignore it, max flow in can not equal max flow out) thus they can’t be full capacity

Question 2

How to write a feasible flow, easiest way

Final check?

Answer 2

Must find a CUT in network = ti this flow

Now saturate all the ones going from source to sink, leave the sink to source untouched

Now must trial and error here, make as many things 0 and do flow in = flow out

As a final check, chekc flow in source = flow out from sink = value you want!

Question 3

How to prove the

Question 4

If they don’t specify direction and want to find cut what to do

Answer 4

Collur be both ways, thus YOU MUST assume ti goes from source to sink and thus ADD IT ON

Question 5

If they introduce a variable x and say what’s the max flow now even tho you calculated one now to do?

Answer 5

So just add this and say this is now the max flow

But MUST USE ANSWERS FROM BEFORE, if they gave cuts and thus that’s an upper bound to the max flow, you know until then when x takes values in between this is max flow

But when x takes certain value beyond this no max flor as we said this cut is the smallest!
Be vigilant ,