Search code examples
algorithmgraph-theorymax-flowford-fulkersonedmonds-karp

3 max flow prove or disprove small questions

The questions are :

enter image description here

for (a) it seems like it is not true, we can fin an example of the flow growing without e being saturated.

for (b) it seems true, yet i am not sure how to prove it. Maybe because of the min cut max flow theorm, it was on the min cut so it had to grew.

for (c) it seems false. the flow grew because e changed but e might have not grew by exactly 5.

Solution

  • (1) seems true for me - If you managed to increase the maximum flow, it means that you found a new path from the source to the sink (that did not exist before increasing the edge e). So e must be in this new path, but if e was not saturated before, then the path would have existed in the original graph.

    (2) is false. Take a graph like this:

    s --20-- n --20-- t

    Where s is the source and t the sink, there are two min-cuts ({(s, n)} and {(n, t)}), but increasing either (s, n) or (n, t) won't change the maximum flow.

    (3) is false. Take a graph like this:

    s --20-- n --25-- t

    If I increase the capacit of e = (s, n) by 10, then the new maximum flow is 25, but I did not increase the value of e by 5.