将网络建模为有向图

Question

我有一个看起来像这样的网络:

基本上,我想知道如果移除/禁用可以断开源和漏极的绿色圆圈的最小数量.(在这种情况下1)
我已经成功实现了Edmonds-Karp算法,但我不知道如何用有向边建模网络,所以我得到了理想的结果.
如果我只是用容量为1的两个相反的有向边替换节点之间的每个连接,我用EdmondsKarp获得最大流量2,但我只需要移除1个绿色圆圈来打破网络.
如何将网络建模为节点并指向边缘？

Answer 1

您可以将此问题简化为有向图中的标准 s\xe2\x80\x93t 切割问题，然后可以通过 Edmonds\xe2\x80\x93Karp 算法来解决。对于每个顶点 v，创建两个顶点 v_in\n 和 v_out 以及一条有向边 (v_in, v_out)，并为每条边 {v,w} 添加两条有向边 (v_out ,w_in) 和 (w_out , v_in)。那么不难看出，从 s_in 到 t_out 的最大流对应于 s 和 t 之间的最小顶点切割。

\n