Explore BrainMass

Explore BrainMass

    Maximum flow

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com June 3, 2020, 6:05 pm ad1c9bdddf

    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.