2

我试图找到一个反例，但它似乎不存在。但是，也找不到证据。也许有人有什么想法？这是详细信息：

对于具有非零最大流量值的每个 st 流网络，都存在一条边，因此降低该边的容量将降低最大流量的值。这是真的假的吗？

4

1 回答 1

7

这是真的。

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

现在，最小割对应于图中某些边集的容量之和。如果您选择减少这些边缘之一的容量会发生什么？（我会让你解决剩下的证明。）

于 2013-11-11T03:52:59.630 回答