问题是:
对于 (a) 似乎不是这样，我们可以找到一个流量增长但 e 未饱和的例子。
对于 (b) 这似乎是正确的，但我不确定如何证明它。也许是因为 最小割最大流定理，它在最小割上所以它必须增长。
对于 (c) 它似乎是错误的。流量增长是因为 e 发生了变化，但 e 可能不会恰好增长 5。
最佳答案
(1) 对我来说似乎是正确的——如果你设法增加了最大流量，这意味着你找到了一条从源到汇的新路径(在增加边 e 之前不存在) >).所以e一定是在这条新路径上，但是如果e之前没有饱和，那么这条路径就已经存在于原图中。
(2) 是错误的。拿一张这样的图:
s --20-- n --20-- t
其中 s 是源，t 是汇，有两个最小切割({(s, n)} 和 {(n, t)})，但增加(s, n) 或 (n, t) 不会改变最大流量.
(3) 是错误的。拿一张这样的图:
s --20-- n --25-- t
如果我将e = (s, n)的容量增加10，那么新的最大流量是25，但是我没有将 e 的值增加 5。
关于algorithm - 3 max flow prove or disprove 小问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34660310/