algorithm - 3 max flow 证明或反驳小问题

Question

问题是：

对于 (a) 似乎不正确，我们可以找到一个流量在不饱和的情况下增长的示例。

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

对于 (c) 它似乎是错误的。流量增加是因为 e 发生了变化，但 e 可能没有正好增长 5。

Answer 1

(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)by10的容量，那么新的最大流量就是25，但我没有增加eby的值5。

Answer 2

对于 (1)：

通过增加一些边的容量，网络的最大流量从 20 增加到 30，e我们需要证明e在增加之前必须已经饱和。

反过来考虑，e在增加之前没有饱和。在这种情况下，必须存在一条边（或一组边）e'，其中整个流量e也通过e'，并且网络的最大流量受到通过边的容量的限制，e'这样capacity(e') < capacity(e)（否则e会饱和）。

鉴于此，如果我们增加，capacity(e)那么我们仍然处于capacity(e') < capacity(e)网络的最大流量不会受到容量增加的影响的情况。

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

例如：

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

        e'           e

上图展示了最大流受限于e'从源到节点的两条边的容量并且e（从节点到汇）不饱和并且增加e不会增加最大流的矛盾。

然而，

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

        e'           e

在此图中，e已饱和（并且e'未饱和) and increasing the capacity ofe` 到 30（或更多）会将图的最大流量增加到 30。

对于其余的：

• 见霍尔特的回答