福特-福克森算法找到哪个最小割？

Question

在网络中可能存在多个最小割。例如： 上图有四个最小割，而Ford-Fulkerson算法会找到距离源点s更近的一个。那么我们能否说对于所有网络都是这样的呢？也就是说，Ford-Fulkerson算法总是能够找到距离源点最近的割？如果是这样，我们该如何在流网络中形式化地定义“距离源点最近”的概念？

- Apratim Bhattacharyya

---

你找到答案了吗？我想听听答案。有同样的想法 :) - arslan

Answer 1

让我们将割定义为一个包含源点但不包含汇点的顶点集合。最小割有这样的特性：两个最小割的交集也是一个最小割（并集同理）。因此，所有最小割的交集在某种意义上是“最靠近”源点的最小割，因为它是所有其他最小割的子集。

- David Eisenstat

Answer 2

（假设最小割在交集下是闭合的。）

我们声明，最小割（最近的割）的交集正好是FF返回的割。以下是证明的大致草图。

从最大流最小割定理中，我们建立了以下结果：

割是最小的，当且仅当每个离开它的边都完全饱和，即f（e）= c（e）。

因此，为推导矛盾，假设存在一个比FF返回的割更接近源的最小割C = Ca，Cb，我将其称为F = Fa，Fb。

然后取边缘e =（v，w），使得它在Fa中但现在不在Ca中（它是Ca的出边）。这条边必须是完全饱和的。因此按照残留图的定义，在残留图中只会有反向边（w，v），那么节点w将无法到达-然而w在Fa中，所以它必须是可达的，这是矛盾的。

- AndW