algorithm - 寻找流网络的最小割

Question

我正在尝试找到以下网络的最小切割

我正在使用以下算法：

1. 运行 Ford-Fulkerson 算法并考虑最终的残差图。

2. 在残差图中找到从源可到达的顶点集。

3. 从可达顶点到不可达顶点的所有边都是最小割边。打印所有这些边缘。

第一步，我的算法找到了 3 条路径：

 - s->b->h->t  **value: 1** 
 - s->d->e->t  **value: 1**
 - s->c->h->i->m->d->g->t  **value: 0.5**

所以最大流量（因此最小切割）等于 2.5。

但是，当我后来尝试从网络中消除上述路径时，我最终得到了这样的结果：

可达顶点是 s、c 和 h，它们形成一个等于 3.5 的割。

我错过了什么？为什么我不能像通常那样遍历图表以获得最小切割？

Answer 1

每次在残差图中增加一条边的容量时，都需要将对边的容量增加相同的量。

示例图：

这是没有后向边的残差图和可到达的顶点集S（不构成最小割）：

以及带有最小切割的正确残差图：

Answer 2

我假设，你对残差图的定义是你把边 A->B 放在残差图中，如果：

a) 在 A->B 方向（又名前向边缘）的流量和容量之间存在一些差异 b) 在 B->A 方向（又名后向边缘）上有一些流量

在这个定义中，您的第 2 步是错误的。

要找到最小切割，您只需从一开始就穿过前边缘。现在，您可以将起点可到达的顶点表示为集合 R，将其余顶点表示为集合 R'。现在切割是由 R 和 R' 之间的边缘进行的。并且切口的大小是R和R'之间的流动。