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

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。对于除 v 之外的每个 w，计算从 v 到 w 的最大流量。由于 v 必须在图的全局最小割的一侧，而其他东西必须在另一侧，因此其中一个流将确定全局最小割。

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