模擬網絡向圖

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最大流量（進出）。所以只知道最大流量不會給你最小限度的回答。

定理

最大流最小切割定理指出 在流動網絡，所述最大量流從源到 水槽傳遞的 等於最小容量 其中當在從網絡的特定方式 除去引起情況 沒有流體可以從源 傳遞到信宿

所以，是的，您知道需要移除的流量，但您不知道要以何種方式移除它。我認爲這不是很微不足道，而且你需要專門尋找最小化。