给定一个网络 N，我想找到其中边数最少的最小割。我想:
求最大流量(以Dinitz算法为例)
增加容量函数使得对于每条边e c'(e)=c(e)+1，然后再次使用Dinitz算法计算差值。
该差异将是 mincut 中的最小边数。
但我无法证明这一点。
是不是概念错了？还是我只是在证明它是错误的？
最佳答案
你不能使边的新容量c'(e)=c(e)+1，这是一个错误的证明，因为min cut在这个变换之后可能会改变。可以使新图的容量为c'(e)=c(e)*(|E|+1)+1，其中(|E|+1)要足够大。
关于algorithm - 在流网络的所有最小切割中找到最少的边缘，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38408852/