查找流网络的最小割

Question

我试图找到下面网络的最小割

我使用下面的算法：

1. 润福特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。

然而，当我稍后尝试消除来自网络I结束了这样的上述路径：

可到达顶点是S，C和H，其形成等于3.5的切口。

我错过了什么？为什么我不能像通常那样遍历图表来得到最小值？

Answer 1

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

实施例图：

这里是不向后边缘剩余图和从S的该组顶点的可达（其不构成最小割）：

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

Answer 2

我假定，您的剩余图的定义是，你把边缘A-> B在剩余图，如果：

一个）有流和容量之间的一些不同的方向A-> B（又名向前边沿） b）方向B-> A（又名后沿）有一些流动

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

要找到最小剪裁，您只能从开头走过前缘。现在，您可以将从起点到达的顶点表示为集合R，并将其作为集合R'休息。 现在切割由R和R'之间的边缘完成。 切割的大小是R和R'之间的流动。