2
$\begingroup$

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!

  • 1
    Perhaps you can show that every augmenting path can be chosen so as to increase the number of saturated edges.2012-11-06

1 Answers 1

1

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.

  • 0
    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'$.2015-07-01