是否有算法在無向圖分離源和接收器中查找最小切割

Question

我有一個邊緣加權無向圖和2個節點（通常稱爲源和接收器）。我需要找到一組最小可能重量的邊，將這2個節點分成2個弱分量。

我知道關於Ford-Fulkerson's maximum flow algorithm和他有關有向圖上的maximum flow and minimum cut relation的定理。

我也知道福特 - 福克森最大流算法對無向圖的修改，它用兩個相反的有向邊替換每個無向邊，並同時更新兩者的流向。但與此修改，最大流 - 最小割定理似乎不再有效，因爲下面的無向圖的最小割將無法正確確定：

nodes: 0, 1, 2, 3 
edges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4 
source: 0 
sink: 3 

最大流分鐘切削定理說，最小切削是那些邊緣，流量等於它們的容量，並且通過改進的Ford-Fulkerson即所有的邊緣，這顯然不是正確的切割。

我在無向圖中找到了Stoer–Wagner algorithm for finding a global minimum cut，但這並不是我想要的，因爲這個算法沒有考慮任何源和匯，並且可以找到一個可以讓節點位於同一個組件中的剪切。

是否有任何算法，它可以有效地找到一個無源圖中的最小切割與source和sink，分離這2個指定節點？ 我可以以某種方式修改前面提到的算法，使它們適合我的情況嗎？

Answer 1

您可以使用Ford-Fulkerson算法的一些修改。

1. 首先，你需要找到源和匯之間的最大流量並記住它。
2. 刪除圖中的某條邊。
3. 然後你需要在新圖中找到最大流量。如果最大流量與第一步不同，那麼這個邊緣處於最小切割。
4. 回邊的圖形，選擇一些其他的邊緣，然後轉到步驟2

當你發現的最大流量，只考慮無向邊緣與相同容量的兩個有向邊。