java - 通过枚举对图进行最小分割

Question

我有一个图表，我将其实现为相邻矩阵。这看起来像这样。

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

在我的代码中，矩阵是一个 int[][] 矩阵；

现在我想通过枚举得到这个图的最小值。但我不知道该怎么做。我已经知道一些随机 mincut 算法，但是对于小图，我想通过枚举找到 mincut，就像在 Karger 和 Stein 的算法中，对于 Vertex < 6 的图。这是这个算法的伪代码。

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));
}

有人可以解释一下如何通过枚举找到最小切分吗？

谢谢你。

Answer 1

From Wikipedia:

Thus, the minimum cut problem can be solved in polynomial time by iterating over all choices of s,t\in V and solving the resulting minimum s-t cut problem using the max-flow min-cut theorem and a polynomial time algorithm for maximum flow, such as the Ford–Fulkerson algorithm, though this approach is not optimal. There is a deterministic algorithm for the minimum cut problem with running time O(mn+n^2\log n).[2]

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