查找圖中的最小切割，使給定的頂點斷開

Question

前段時間我讀到了有關一般mininum切割算法，該算法將輸入圖作爲輸入並刪除最小值。邊緣的數量使得兩個斷開的組件保留。

我現在正在研究一個具有10k +節點和500k +邊的無向圖（兩個頂點之間沒有多邊）。爲了賦予節點之間的交互作用，我考慮計算斷開兩個給定頂點（或流量相關度量）的最小切割。

是否有有效的算法爲圖的每對頂點提出一個值（最小割集的基數）？作爲這個主題相當新穎，如果有人能夠提供指向運行時間複雜度合理的論文或其他資源的鏈接，我將深表謝意。

謝謝！

Answer 1

有幾種算法（參見Wiki的介紹）可以找到網絡中的最大流量。我知道的那些人（Ford-Fulkerson，Dinic，Karp-Edmond）應該在單位容量（= 整數容量等於1，在所有邊緣）表現良好（可變容量增加複雜性，並且隨着非整數容量出現更多問題）

對於任何一對頂點，您可以通過將source/sink設置爲該對來從圖中創建一個網絡。您使用其中一種算法獲得最大流量，您可以使用其中一種算法進行如下分析：

• 選擇流所使用的任何邊。這條邊將屬於切割。
• 重複，但是現在沒有做選擇的邊緣（S）上的曲線圖的流動搜索直到流量爲0

最後，你有最小割，尺寸最大流量的。

如果你真的想要表現的話，你可能想看看這篇論文：Andrew V. Goldberg的Flows in Undirected Unit Capacity Networks (1997)，Satish Rao，但我可能會堅持簡單的。