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

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)次max flow算法）而不是O(V^2)个

Answer 1

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

Hao和Orlin有一个诀窍，如果你使用一个预流推算法，一个全局最小割的计算花费的时间和一个最小（s,t）割问题花费的时间差不多。它有实用的好处。Karger有一个随机算法，它在O（n polylog（n））时间内完成，但我不知道任何实现，更别提快速实现了。