使用最大流算法查找网络的边缘连通性

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 |来做这件事 流网络(仅运行最大流算法O(| V |)次)而不是O(| V | ^ 2)

Answer 1

区分v图表中的节点.计算,每一个w比其他v,从最大流量v到w.由于v必须在图的全局最小切割的一边,而另一边必须在另一边,其中一个流将识别全局最小切割.

由于Hao和Orlin,有一个技巧,如果使用预流推送算法,全局最小切割计算需要与最小(s,t)切割问题一样多的时间.它具有实用性的好处.Karger有一个随机算法,它在O(n polylog(n))时间内完成,但我不知道任何实现,更不用说快速实现了.