algorithm - 检查给定网络流中是否存在单个最小割

Question

我正在寻找一种算法来检查给定网络流中是否存在最小切割。

我知道这是可能的，因为我们可以寻找所有的切割，并检查我们是否只有 1 个最小切割，但我想找到更高效的多项式运行算法。

我想过使用最大流算法来帮助我，但我没有成功。

Answer 1

我假设您指的是加权情况，如果不是 - 通过为所有边赋予 1 的权重，可以很容易地将未加权的情况减少为加权情况。

一种方法是找到一个最小切割，让它成为 U1、U2 的分割，然后对于 U1 中的每一对顶点 u1 和 U2 中的 u2，这样 (u1,u2) 在 E 中 - 检查是否通过稍微增加权重 w(u1,u1) - 仍然有一个具有相同值的最小切割。
最后，当且仅当您找到一条边使得最小切割值保持不变时 - 存在不止一个最小切割。

高级伪代码:

value,U1,U2 = min-cut(G) //value is the minimum cut value, U1,U2 are the cuts
for each u1 in U1 and u2 in U2 such that (u1,u2) is in E:
   temp <- w(u1,u2)
   w(u1,u2) <- w(u1,u2) + epsilon
   new_value,_,_ = min-cut(G)
   if (new_value == value): //2+ cuts with same value
        return true
   //roll back the changed weight
   w(u1,u2) <- temp
return false //no cuts with same value found

复杂度是O(E*min-cut)，其中min-cut是使用的min-cut算法的复杂度