图由枚举Mincut

问题描述

限时删除！！

我有我实现为邻接矩阵图。这看起来是这样的。

I have a graph which I implemented as an adjacent matrix.This looks like this.

       v1 v2 v3 v4
    v1 0  1  0  2
    v2 1  0  3  0
    v3 0  3  0  0
    v4 2  0  0  0

在我的code矩阵是一个    INT [] []矩阵;

In my code the matrix is an int[][] Matrix;

现在我想通过枚举得到这个图的mincut。但我不知道如何做到这一点。我已经知道了一些随机mincut算法，但对于小图我想找到mincut通过枚举像卡格尔和Stein的图形顶点和其中的算法; 6。下面是该算法中的伪code。

Now I want to get the mincut of this graph by enumeration. But I dont know how to do this.I already know some random mincut algorithm but for small graphs I want to find the mincut by enumeration like in the algorithm of Karger and Stein for graphs with Vertex < 6.Here is pseudo code of this algo.

mincut() {
if(V<6)
    <return mincut by enumeration>
else
    t=1+n/sqrt(2)
    G1 = contract(G,t)
    G2 = contract(G,t)
    return min(mincut(G1),mincut(G2));
}

可能有人请解释我如何找到mincut通过枚举？

Could someone please explain me how to find the mincut by enumeration?

感谢你。

推荐答案

从百科：

因此​​，最小割问题可以在多项式时间内通过迭代的S，T \所有选择在V和使用的最大流最小割定理以及多项式算法的最大流量，如的，尽管这种方法不是最优的。没有为最小割问题确定的算法与运行时间为O（MN + N ^ 2 \日志N）。[2]

该算法是拼写出来，你在这里：的Stoer - 瓦格纳MIN-切割算法你可以找到它的第3页。

The algorithm is spelled out for you here: The Stoer-Wagner Min-cut Algorithm You can find it on Page 3.

这篇关于图由枚举Mincut的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

1403页，肝出来的..