无反向图的计算最小剪切

Question

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

我想在集合S和T中找到图G的Min-Cut，其中从T到S没有边缘。此示例图找到一个最小切割（幅度为250），但结果具有从T到S的边缘（红色）。

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9UQ1NYUy5wbmcifQ==” alt =“在此处输入图像描述”>

有人知道是否存在解决此问题的算法？还是有办法修改流量网络，以便使用福特福特福克森之类的东西？

我知道您可以使用像Ford-Fulkerson这样的Max-Flow算法，并通过Max-Flow / Min-Cut定理找到一个Min-Cut。但是，这并不是我需要计算的最小剪切类型。我想找到...

Answer 1

我相信这应该起作用：对于每个边缘，添加具有无限容量的反向边缘。这样，如果最小切割是有限的，则原始边只能从S到T，而不能反过来。