减少某些边的容量将会降低最大流量。

Question

3

我正在寻找反例，但似乎并不存在。然而，也没有找到证明。也许有人有些想法？以下是详细信息：

对于每个具有非零最大流值的s-t流网络，存在一条边，使得减小该边的容量将减少最大流的值。这是真的还是假的？

- Simo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dennis Meng · Accepted Answer

这是真的。

Ford和Fulkerson证明了最大流最小割定理，该定理基本上说明了图的最大流等于最小割。

现在，最小割对应于图中某些边的容量之和。如果您选择减少其中一条边的容量会发生什么？（我让您自己推导出其余的证明。）