計算沒有反向邊的圖的最小切割

Question

我知道你可以使用像福特 - 福克森這樣的最大流算法，並用最大流/最小切割定理找到最小切割。但是，這不完全是我需要計算的Min-Cut的類型。

我想找到圖G的最小割集成S和T，其中有在T至S沒有邊緣。

本示例圖找到最小切割（250級），但結果有從T到S（紅色）的邊緣。

有誰知道，如果有一個現有的算法來解決這個問題？或者如果有一種方法可以修改我的流量網絡，那麼我可以使用像Ford-Fulkerson這樣的東西？

Answer 1

我認爲這應該工作：對於每個邊緣，添加無限容量的反向邊緣。這樣，如果最小切割是有限的，原始邊只能從S到T，而不是相反。