通过最大流量算法查找网络边缘连接 [英] Finding edge connectivity of a network by using Maximum Flow algorithm

问题描述

我想找到的边缘连接（边缘即最小数删除，断开图），使用最大流算法（埃德蒙·卡普/福特Fulkerson增算法）无向图中，

I want to find the edge connectivity (i.e. minimum number of edges to remove to disconnect a graph) of an undirected graph using maximum flow algorithms (Edmond Karp / Ford-Fulkerson algorithms) ,

我知道我可以通过找到的曲线图的每两个节点之间的最小的最大流量完成这个任务，但这样会导致O（| V | ^ 2）个流网络的，

I know that I can accomplish this task by finding the minimum maximum flow between every two nodes of a graph , but this would result O(|V| ^ 2) number of flow networks ,

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）其中

But I'd like to do this with |V| flow networks (running the max flow algorithm for only O(|V|) times) instead of O(|V| ^ 2) of them

推荐答案

区分在图形中的节点 v 。计算，为每是W 比 v ，另外从最大液流V 到是W 。由于 v 必须是在图形上的全球最小割的一个湖畔，别的东西必须是在另一边，一是这些流量将确定全球最小割的。

Distinguish a node v in your graph. Compute, for every w other than v, the maximum flow from v to w. Since v must be on one shore of the graph's global minimum cut and something else must be on the other side, one of these flows will identify the global minimum cut.

还有，由于在那里，如果你使用了preflow推进算法浩的Orlin一招，全球最小割计算大约需要尽可能多的时间最少（S，T）-cut问题。它具有务实的利益。卡尔格有一个随机算法，做它为O（n polylog（n））的时间，但我不知道有任何的实现，更不用说快速实现。

There's a trick due to Hao and Orlin where, if you use a preflow push algorithm, a global minimum-cut computation takes about as much time as a minimum (s,t)-cut problem. It has the benefit of being practical. Karger has a randomised algorithm that does it in O(n polylog(n)) time, but I'm not aware of any implementations, let alone fast implementations.

这篇关于通过最大流量算法查找网络边缘连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！