algorithm - Ford-Fulkerson 算法找到哪个最小割？

Question

网络中可以有多个最小切割。例如：

有四个最小切割，Ford-Fulkerson 找到一个“更接近” s（源）。我们可以对所有网络都说同样的话吗？也就是说，Ford-Fulkerson 找到离源最近的切口？如果为真，我们如何将流网络中“最接近源”的概念形式化？

Answer 1

让我们将切割表示为一组包含源但不包含汇的顶点。最小割具有两个最小割的交集是最小割的性质（这也适用于联合）。因此，所有最小割的交集在某种意义上是离源“最近”的最小割，因为它是所有其他最小割的子集。

Answer 2

（假设最小切割在交叉点下是闭合的。）

我们声称最小割的交集（最接近的割）正是 FF 返回的割。这是一个证明的粗略草图。

根据 MaxFlow MinCut Theorem，成立以下结果：

如果每条离开它的边都完全饱和，则切割是最小的，即 f(e) = c(e)。

因此，为了矛盾，假设有一个最小切割 C = Ca, Cb，它比 FF 返回的更接近源，我将其称为 F = Fa, Fb。

然后取边 e = (v, w) 使得它在 Fa 中但现在不在 Ca 中（它是 Ca 的出边）。该边缘必须完全饱和。因此，根据残差图的定义，残差图中只有后向边 (w, v)，然后该节点 w 将无法到达 - 但 w 在 Fa 中，因此它一定是可到达的，这是一个矛盾。