Mincut of graph by enum

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 

В моем коде матрица является ИНТ [] [] Matrix;

Теперь я хочу получить mincut этого графа путем перечисления. Но я не знаю, как это сделать. Я уже знаю некоторый случайный алгоритм сокращения, но для небольших графов я хочу найти mincut путем перечисления, как в алгоритме Каргера и Штейна для графов с вершиной < 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)); 
} 

Может кто-нибудь объяснить мне, как найти mincut путем перечисления?

спасибо.

Answer 1

От Wikipedia:

Таким образом, минимальная проблема разреза может быть решена за полиномиальное время путем перебора все выбора S, T \ в V и решая полученную минимальную й проблему разреза с помощью max-flow min-cut theorem и полином временной алгоритм для максимального потока, такой как Ford–Fulkerson algorithm, хотя этот подход не является оптимальным. Существует детерминированный алгоритм для задачи минимального разреза с временем выполнения O (mn + n^2 \ log n). [2]

алгоритм пишется для вас здесь: The Stoer-Wagner Min-cut Algorithm Вы можете найти на странице 3.