3 max flow prove or disprove 小问题

Question

问题是：

对于 (a) 似乎不是真的，我们可以找到一个流量增长的例子，而 e 没有饱和。

对于 (b) 这似乎是正确的，但我不确定如何证明它。也许是因为最小切割最大流量定理，它在最小切割上所以它必须增长。

对于 (c) 来说，这似乎是错误的。流量增长是因为 e 发生了变化，但 e 可能并未恰好增长 5。

Answer 1

(1) 对我来说似乎是正确的——如果你设法增加了最大流量，这意味着你找到了一条从源到汇的新路径（在增加边缘之前不存在 e ).所以e一定是在这条新的路径上，但是如果e之前没有饱和，那么这条路径在原来的图中就已经存在了。

(2) 为假。采取这样的图表：

s --20-- n --20-- t

其中 s 是源，t 是汇，有两个 min-cuts（{(s, n)} 和 {(n, t)}），但增加任一 (s, n)或(n, t)不会改变最大流量。

(3) 为假。采取这样的图表：

s --20-- n --25-- t

如果我把e = (s, n)的容量增加10，那么新的最大流量就是25，但是我没有把e的值增加5.

Answer 2

对于 (1)：

The max-flow of the network has increased from 20 to 30 by increasing the capacity of some edge e and we need to prove that e must have been saturated before the increase.

反之，e 在增加之前没有饱和。在这种情况下，必须存在一条边（或一组边）e'，其中通过 e 的整个流也通过 e'，并且网络的 max-flow 是受通过边缘 e' 的容量限制，使得 capacity(e') < capacity(e)（否则 e 将饱和）。

鉴于此，如果我们增加 capacity(e) 那么我们仍然处于 capacity(e') < capacity(e) 的情况，网络的 max-flow 将不受增加容量的影响。

这是一个矛盾（因为增加e的容量增加了max-flow）；所以 e 必须饱和 （你可以进一步注意如果 e' 存在那么它不能饱和，因为 max-flow 增加了）.

例如：

    /-- 10 --\ 
source      node -- 30 -- sink
    \-- 10 --/

        e'           e

上图展示了矛盾，其中 max-flow 受从源到节点的两条边 e' 的容量限制，而 e（从节点到汇）不是饱和和增加 e 不会增加 max-flow.

然而，

    /-- 15--\ 
source      node -- 20 -- sink
    \-- 15 --/

        e'           e

在此图中，e 饱和（而 e' 未饱和) and increasing the capacity ofe` 到 30（或更多）将增加图形的 max-flow到 30.

其余的：

见

3 max flow prove or disprove 小问题

3 max flow prove or disprove small questions

algorithm

graph-theory

max-flow

ford-fulkerson

edmonds-karp