给定网络 G=(V,E) 、最大流 f 和 E 中的边 e ，我需要找到一个有效算法来检测是否存在包含 e 的最小割。 另一个问题是，如果我发现 e 包含在某个最小切割中，是否可以检测它是否是切割中最轻的边缘？
我考虑过运行 Ford-Fulkerson 算法，增加/减少给定边缘的容量，看看会发生什么，但我还没有想出可以帮助我解决问题的方法。
如果有人能指出我的解决方案，我将不胜感激，在此先感谢。
最佳答案
这里是第一个问题的解决方案:假设w(e)是e的权重，计算G的min-cut值>，假设是 C。然后我们从 G 中删除 e 以生成 G'；我们再次计算G'的最小切割值，假设是C'，如果C-C'>=w(e)，那么这就得出e，参与了至少一个min-cut(你已经知道了)，否则e不属于任何min-cut。
关于algorithm - Max-Flow - 检测是否在某个最小切割中找到给定边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16984852/