将网络建模为有向图

Question

我有一个网络，可能是这样的：

基本上，我想知道如果移除/禁用，可以断开源极和漏极的最小绿色圆圈数。(在本例中为1)

我已经成功地实现了Edmonds-Karp算法，但我不知道如何用有向边来建模网络，所以我得到了想要的结果。

如果我只是将节点之间的每个连接替换为容量为1的两条相反的有向边，我使用EdmondsKarp得到的最大流量为2，但我只需要删除1个绿色圆圈就可以断开网络。

如何将我的网络建模为节点和定向边缘？

Answer 1

你可以将这个问题简化为有向图中的标准s-t割问题，然后可以用Edmonds-Karp算法来解决。对于每个顶点v，创建两个顶点v_in和v_out以及一个有向边(v_in，v_out)，并为每个边{v，w}添加两个有向边(v_out，w_in)和(w_out，v_in)。因此不难看出，从s_in到t_out的最大流对应于s和t之间的最小顶点切割。

Answer 2

您已正确确定最大流量-您的网络的最大流量为2。

来自flow network的定义

流必须满足以下限制，即流入节点的流量等于流出该节点的流量，除非它是传出流量较多的源或传入流量较多的宿

因此，对于中间节点，最大流量为2(传入和传出)。因此，只知道最大流量不会给你最小切割的答案。

定理

最大流最小截断定理指出，在流网络中，从源端到汇端的最大流量等于最小容量，当以特定方式从网络中移除该最小容量时，将导致没有流可以从源端通过到汇端。

所以，是的，你知道你需要删除的流量，但是你不知道用哪种方式删除它。我认为这并不是那么微不足道，你需要特别去寻找min-cut。