algorithm - Max-Flow - 检测是否在某个最小切割中找到给定的边缘

Question

给定一个网络 G=(V,E) ，一个最大流 f 和一个 E 中的边 e，我需要找到一个 efficeint 算法来检测是否存在一些包含 e 的最小割。另一个问题是，如果我发现 e 包含在某个最小切割中，是否可以检测它是否是切割中最轻的边缘？

我考虑过运行 Ford-Fulkerson 算法，并增加/减少给定边缘的容量，看看会发生什么，但我还没有想出一些可以帮助我解决问题的方法。

如果有人能指出我的解决方案，我将不胜感激，在此先感谢。

Answer 1

这是第一个问题的解决方案：假设w(e)是 的权重e，计算 的最小切割值G，假设是C。然后我们e从Gto make中删除G'；我们再次计算 的最小割值G'，假设是C'，如果C-C'>=w(e)，则得出e，参与至少一个最小割（你已经知道它），否则e不属于任何最小割。