Ford-Fulkerson算法找到哪种最小切割？

Question

网络中可以有多个最小割.例如:

有4个小时削减,福特 - 富尔克森找到了一个"更接近"s(来源).我们可以对所有网络说同样的话吗？也就是说,Ford-Fulkerson发现最接近源头的切口？如果是的话,我们如何在流动网络中形成"离源最近"的概念？

Answer 1

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