在流网络中找到所有最小割中边数最少的割。

Question

3

给定一个网络N，我想找到具有最少边数的最小割。我考虑了以下方法：

1. 找到最大流（例如使用Dinitz算法） 2. 增加容量函数，使得对于每条边e，c'(e)=c(e)+1，然后再次使用Dinitz算法并计算差异。 3. 那个差异将是mincut中的最小边数。

但我陷入了证明中。

这个概念是错误的吗？还是我只是在错误地证明它？

- Yinon Eliraz

1个回答

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

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

- Qianyang Peng · Answer 1

您不能将边缘 c'(e)=c(e)+1 的新容量，这是错误的证明，因为此转换后最小割可能会改变。您可以将新图的容量 c'(e)=c(e)*(|E|+1)+1，其中 (|E|+1) 应足够大。