模拟网络向图 [英] Modeling network as directed graph

问题描述

我有一个看起来是这样的一个网络：

基本上，我想知道绿色的圆圈可以断开源，如果删除/禁用漏的最低数量。 （在这种情况下，1）
我已经成功地实施了埃德蒙兹 - 卡普algrorithm，但我不知道如何在网络中向边模式，让我得到了想要的结果。
如果我只是更换两个相对向边容量1节点之间的每个连接，我得到了2 EdmondsKarp一个最大流量，但我只需要移除1绿圈打破了网络。
我如何将网络建模为节点，并指示小幅？

I have a network that could look like this:

Basically, I want to know the minimum number of green circles that can disconnect the source and drain if removed/disabled. (in this case 1)
I have already succesfully implemented the Edmonds-Karp algrorithm, but I don't know how to model the network with directed edges, so I get the desired result.
If I just replace each connection between the nodes with two opposite directed edges with capacity 1, I get a max flow of 2 with EdmondsKarp, but I only need to remove 1 green circle to break the network.
How do I model my network as nodes and directed edged?

推荐答案

您可以向图减少这个问题，以标准的S-T切的问题，这样就可以解决的，例如由埃德蒙 - 卡普算法。对于每个顶点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之间的最小顶点晋级。

You can reduce this problem to the standard s–t cut problem in directed graphs, which can then solved e.g. by the Edmonds–Karp algorithm. For each vertex v, create two vertices v_in and v_out and a directed edge (v_in, v_out), and for each edge {v,w}, add two directed edges (v_out ,w_in) and (w_out , v_in). It is then not hard to see that a maximum flow from s_in to t_out corresponds to a minimum vertex cut between s and t.

这篇关于模拟网络向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！