Explore BrainMass

Maximum flow

Is it true that if I multiply all the edge capacities in an s-t flow problem by a positive constant k > 0, then the maximum flow increases by the same factor of k.

Solution Preview

Yes it is

the sum of the capacities of the arcs on the minimal cut equals the maximum flow is a famous theorem of network theory called the max flow min cut theorem

for example

Let minimal cuts of arcs in s-t flow are ...

Solution Summary

This verifies a statement regarding edge capacities and maximum flow.