algorithm - 计算无反边图的最小割

Question

我知道您可以使用像 Ford-Fulkerson 这样的 Max-Flow 算法，并使用 Max-Flow/Min-Cut 定理找到 Min-Cut。但是，这并不是我需要计算的 Min-Cut 类型。

我想找到图 G 到集合 S 和 T 的 Min-Cut，其中<​​strong>从 T 到 S 没有边。

此示例图找到一个最小割(量级为 250)，但结果有一条从 T 到 S 的边(红色)。

有谁知道是否有解决此问题的现有算法？或者，如果有一种方法可以修改我的流量网络，以便我可以使用 Ford-Fulkerson 之类的东西？

Answer 1

我相信这应该可行:对于每条边，添加一条具有无限容量的反向边。这样，如果最小切割是有限的，则原始边只能从 S 到 T，而不是相反。