用最大流算法求网络的边连通性

Question

我想使用最大流算法(Edmond Karp / Ford-Fulkerson算法)找出无向图的边连通性(即，要移除以断开图的最小边数)，

我知道我可以通过找到图的每两个节点之间的最小最大流来完成这项任务，但这将导致O(|V| ^ 2)个流网络，

int Edge-Connectivity(Graph G){
    int min = infinite;
    for (Vertex u: G.V){
        for (Vertex v: G.V){
           if (u != v){ 
             //create directed graph Guv (a graph with directed edges and source u and sink v)
             //run Edmonds-Karp algorithm to find the maximum flow |f*|
             if (min > |f*|)
               min = |f*|;
           }    
         }
     }
     return min;
}

但我希望使用|V| flow网络(运行最大流算法仅运行O(|V|)次)，而不是O(|V| ^ 2)次

Answer 1

在图中区分节点v。对于除v之外的每个w，计算从v到w的最大流量。由于v必须在图的全局最小割线的一边，而另一边必须有其他东西，因此这些流中的一个将标识全局最小割线。

Hao和Orlin有一个技巧，如果你使用预流推算法，全局最小割集计算所需的时间与最小(s，t)-cut问题的时间差不多。它的好处在于它是实用的。Karger有一个随机算法，可以在O(n polylog(n))时间内完成，但我不知道有任何实现，更不用说快速实现了。