Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to show that a maximum flow in a network $G = (V;E)$ can always be found by a sequence of at most $|E|$ augmenting paths. A hint that was given to me was to determine the paths after finding the maximum flow.

Appreciate all the help. Thanks!

share|improve this question
1  
Welcome to math.SE community! Please, acquaintance yourself with the FAQ, it is really helpful (among others there are some tips for how to make your questions/answers readable). Also, from the wording of your question I suspect that it might be a homework problem. Please note, that there is a (homework) tag, it will cause that you will get not only solution, but probably also a lot of useful hints how to work it out yourself. On the other hand, homework assignments without the (homework) tag are treated really badly. Good luck! –  dtldarek Nov 6 '12 at 11:12
1  
Perhaps you can show that every augmenting path can be chosen so as to increase the number of saturated edges. –  Gerry Myerson Nov 6 '12 at 11:20
add comment

1 Answer

I'll reformulate the statement a bit to avoid ambiguity (although it is possible that the ambiguity is only in my head due to my poor knowledge of English): in any network $G=(V, E)$ there exists a maximum flow $f$ that can be found by a sequence of at most $|E|$ augmenting paths.

One way to prove that is by considering a maximum flow $f$ that has the minimal possible value of $\sum_{u,v \in V} |f(u, v)|$. Such a flow exists, because the space of all max flows is compact and the function $f \to \sum_{u,v \in V} |f(u, v)|$ is continuous.

Now consider a new graph $G'=(V, E')$ where $E'=\{(u,v)|f(u, v)>0\}$. It is easy to prove that since $\sum_{u,v \in V} |f(u, v)|$ is minimal, this graph $G'$ is acyclic. Now it is quite easy to see that flow $f$ can be found by a sequence of at most $|E'|$ augmenting paths whose edges belong to $E'$.

NOTE: about that ambiguity that I mentioned earlier. If the statement actually means that any maximum flow can be found by a sequence of at most $|E|$ augmenting paths, then it is simply not true. To build a counterexample one can just take any network and attach to it a new cycle (somewhere on the side) with huge edge capacities, and send a huge flow along that cycle. To build such a flow one would need to augment the flow a huge number of times.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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