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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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

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|cite|improve this answer
    
Could you please explain this. > 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'$. – gkb0986 Jul 1 '15 at 4:20

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.