CODEWITHSUNDEEP
algorithmdata-structuresgraphnetwork-flow
user4556130
user4556130

Reputation:

Maximum Flow and Some Condition

Suppose we have a Directed Graph and each edges has a positive capacity. if C is a positive constant, i say, if we add or subtract C to all edges capacity, the maximum flow, changed, (maybe increase or decrease). my question is, why if we multiply all edges capacity into C, the maximum flow is product by C?

why this is true?

Upvotes: 0

Views: 324

Answers (1)

amit
amit

Reputation: 178451

The claim is true, because the maximum flow is also the min cut.

Let the old capacity be w:E->N, and the new capacity w':E->N such that w'(e) = C*w(e)

The min cut is the sum of w'(e_i) for each e_i in the cut, but since w'(e_i) = C*w(e_i), we can say that the min cut is sum (C*w(e_i)) = C * sum(w(e_i)).

In addition, since for every cut X: sum(w(e_i) | e_i in min cut) <= sum(w(e_i) | e_i in cut sum X), by multiplying with any constant C we get that:

C* sum(w(e_i) | e_i in min cut) <= C*sum(w(e_i) | e_i in some cut X)
sum(C * w(e_i) | e_i in min cut) <= sum(C*w(e_i) | e_i in some cut X)
sum(w'(e_i) | e_i in min cut) <= sum(w'(e_i) | e_i in some cut X)

And thus, the "old" min cut is also the "new" min cut (multiplied by C), and thus the overall max flow of the network increased by a factor of C.

Upvotes: 4

Related Questions