寻找流网络的最小切割
Finding minimal cut of a flow network
我正在尝试找到以下网络的最小割
我正在使用以下算法：
运行 Ford-Fulkerson算法并考虑最终残差图
在残差图中找到从源可达的顶点集。
所有从可达顶点到不可达顶点的边都是最小割边。打印所有这样的边。
在第一步中，我的算法找到了 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的割。
我错过了什么？为什么我不能像通常那样遍历图形以获得最小割？
我假设，您对残差图的定义是，如果满足以下条件，您将边 A->B 放入残差图中：
a) A->B 方向（也称为前向边缘）的流量和容量之间存在一些差异
b) 在 B->A 方向（也称为向后边缘）
有一些流动
在此定义中，您的第 2 步是错误的。
要找到最小割，您只需从头开始遍历前向边缘。现在您可以将从起点可达的顶点表示为集合 R，将其余部分表示为集合 R'。
现在由 R 和 R' 之间的边进行切割。
并且切割的大小是R和R'之间的流。
残差图中每增加一条边的容量，就需要将对边的容量增加相同的量。
示例图表：
这里是没有后向边的残差图和从S可达的顶点集（不构成最小割）：
以及带最小割的正确残差图：
我正在尝试找到以下网络的最小割
我正在使用以下算法：
运行 Ford-Fulkerson算法并考虑最终残差图
在残差图中找到从源可达的顶点集。
所有从可达顶点到不可达顶点的边都是最小割边。打印所有这样的边。
在第一步中，我的算法找到了 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的割。
我错过了什么？为什么我不能像通常那样遍历图形以获得最小割？
我假设，您对残差图的定义是，如果满足以下条件，您将边 A->B 放入残差图中：
a) A->B 方向（也称为前向边缘）的流量和容量之间存在一些差异 b) 在 B->A 方向（也称为向后边缘）
有一些流动在此定义中，您的第 2 步是错误的。
要找到最小割，您只需从头开始遍历前向边缘。现在您可以将从起点可达的顶点表示为集合 R，将其余部分表示为集合 R'。 现在由 R 和 R' 之间的边进行切割。 并且切割的大小是R和R'之间的流。
残差图中每增加一条边的容量，就需要将对边的容量增加相同的量。
示例图表：
这里是没有后向边的残差图和从S可达的顶点集（不构成最小割）：
以及带最小割的正确残差图：