有向图中的最小 cut/maximum 流
Minimal cut/maximum flow in directed graph
我有一个有向图
首先，我使用了Ford-Fulkerson的算法来增加网络的流量。当我标记顶点时，我看到路径上的流：s->a->b->d->t 可以增加一个，因此图形更改为：
我知道在搜索最大流时，需要将连接图的最小割和外部的所有边的容量加起来。
我的最小切割包含顶点：s, a, c，所以当我将所有边加起来时，我得到 c(G, !G) = 3 + 2 +2 + 1，但是，这比流向 t（5）大很多。
我做错了什么，我搞砸了 FF 或最小切割？
你的最小削减不是s, a, c，而是s, a, b, c。它的容量是5，这是你计算的最大流量。
你可以使用残差网络的定义找到最小割。回想一下，当残差网络中 s 和 t 之间没有路径时，Ford-Fulkerson 终止。
最小割(S,T)定义为
S = { v | there exists a path from s to v in the residual network }
在您的图表中，节点 b 可从残差网络中的 c 到达，因为流 b->c 的权重为 3。
我有一个有向图
首先，我使用了Ford-Fulkerson的算法来增加网络的流量。当我标记顶点时，我看到路径上的流：s->a->b->d->t 可以增加一个，因此图形更改为：
我知道在搜索最大流时，需要将连接图的最小割和外部的所有边的容量加起来。
我的最小切割包含顶点：s, a, c，所以当我将所有边加起来时，我得到 c(G, !G) = 3 + 2 +2 + 1，但是，这比流向 t（5）大很多。
我做错了什么，我搞砸了 FF 或最小切割？
你的最小削减不是s, a, c，而是s, a, b, c。它的容量是5，这是你计算的最大流量。
你可以使用残差网络的定义找到最小割。回想一下，当残差网络中 s 和 t 之间没有路径时，Ford-Fulkerson 终止。
最小割(S,T)定义为
S = { v | there exists a path from s to v in the residual network }
在您的图表中，节点 b 可从残差网络中的 c 到达，因为流 b->c 的权重为 3。