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)

因此，“旧”最小切割也是“新”最小切割（乘以 C），因此网络的整体最大流量增加了 C 倍。