没有反向边的图的最小割问题求解

Question

4

我知道你可以使用像Ford-Fulkerson这样的最大流算法，并使用最大流/最小割定理找到最小割。然而，这不是我需要计算的确切类型的最小割。

我想要找到图G的最小割，将其分成集合S和T，其中不存在从T到S的边。

这个例子图找到了一个最小割（大小为250），但结果有一条从T到S的边（红色）。

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

- realmatt

我正在尝试解决一个不同的问题，将其转化为图分割问题。它有一个限制条件，即一个集合只能从另一个集合接收数据。 - realmatt

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niklas B. · Accepted Answer

我认为这应该可行：对于每一条边，添加一条反向边，并赋予无限容量。这样，如果最小割是有限的，原始边只能从S到T，而不能反过来。