最大流量和一些条件

Question

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

为什么这是真的？

Answer 1

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

设旧容量为 w:E->N，新容量为 w':E->N，使得 w'(e) = C*w(e)

最小切割是切割中每个 e_i 的 w'(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)

因此，"old" min cut 也是 "new" min cut（乘以 C），因此网络的整体最大流量增加了 C 倍。