algorithm - 最大流量和一些条件

Question

假设我们有一个有向图，并且每条边都具有正容量。如果 C 是一个正常数，我说，如果我们将 C 添加或减去所有边的容量，最大流量就会改变(可能增加或减少)。我的问题是，为什么如果我们将所有边的容量乘以 C，最大流量就是 C 的乘积？

为什么这是真的？

Answer 1

这个说法是正确的，因为最大流量也是最小割。

设旧容量为w:E->N , 和新产能 w':E->N这样 w'(e) = C*w(e)

最小切割是 w'(e_i) 的总和对于每个 e_i在剪辑中，但自w'(e_i) = C*w(e_i) , 我们可以说最小割是 sum (C*w(e_i)) = C * sum(w(e_i)) .

另外，因为对于每一次切割 X:sum(w(e_i) | e_i in min cut) <= sum(w(e_i) | e_i in cut sum X) , 乘以任何常数 C我们明白了:

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)

因此，“旧”最小割也是"new"最小割(乘以 C)，因此网络的整体最大流量增加了 C 倍。