6

我想使用最大流算法（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)

4

1 回答 1

7

区分图中的节点v。计算从w到的v最大流量。由于必须在图的全局最小割的一侧，而另一侧必须有其他东西，这些流中的一个将识别全局最小割。vwv

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

于 2013-05-05T12:46:12.377 回答