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 算法的复杂度