4
$\begingroup$

Let's say we a have flow network with $m$ edges and integer capacities.

Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.

A good way to start thinking about this is to imagine that we know the maximum flow already. How can we figure the sequence of $m$ paths?

Improve this question
$\endgroup$
8
  • $\begingroup$ Have you looked at runtime analyses of the Ford-Fulkerson algorithm? $\endgroup$
    – Raphael
    Commented Apr 14, 2013 at 16:12
  • $\begingroup$ The run-time analysis shows that the upper limit for the iterations in "the loop" is determined by the maximum capacity C. In the worst case scenario with the increments of 1 the algorithm roughly runs C times. $\endgroup$
    – 372
    Commented Apr 14, 2013 at 18:25
  • $\begingroup$ why do you think this is true? $\endgroup$
    – Sasho Nikolov
    Commented Apr 14, 2013 at 19:47
  • $\begingroup$ This is a problem from one of the books. I think it is obvious that the problem is not trivial $\endgroup$
    – 372
    Commented Apr 14, 2013 at 20:15
  • $\begingroup$ The Ford-Fulkense runtime analysis suggests the running time of O(N*f) where f is the largest flow in the network. This is natural because determination of a single path roughly takes O(N) and for integer maximum flow of f the algorithm iterates f times. So the non-trivial part is to prove that if paths were to be chosen in an optimal way the number of iterations would actually be N. $\endgroup$
    – 372
    Commented Apr 14, 2013 at 22:31

2 Answers 2

Reset to default
2
$\begingroup$

I got it myself... The idea is to set the flows of all edges to 0 one by one. It will take M iterations to do so. Once all edges are set to zero it becomes clear that the highest number of augmenting paths can not exceed the number of edges that are 0.And since there are M such edges the maximum number of possible paths is M as well.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Here is the solutions from my university exercise sheet. But frankly speaking I still don't get it...

Solution from my exercise sheet

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.