Нахождение минимального разреза в графе с помощью алгоритма Крускала?

We have already seen that spanning trees and cuts are intimately related. Here is another connection. Let’s remove the last edge that Kruskal’s algorithm adds to the spanning tree; this breaks the tree into two components, thus defining a cut (S,S) in the graph. What can we say about this cut? Suppose the graph we were working with was unweighted, and that its edges were ordered uniformly at random for Kruskal’s algorithm to process them. Here is a remarkable fact: with probability at least 1/n^2, (S,S) is the minimum cut in the graph, where the size of a cut (S, S) is the number of edges crossing between S and S. This means that repeating the process O(n^2) times and outputting the smallest cut found yields the minimum cut in G with high probability: an O(mn^2 log n) algorithm for unweighted minimum cuts. Some further tuning gives the O(n^2 log n) minimum cut algorithm, invented by David Karger, which is the fastest known algorithm for this important problem.

• Разве это не зависит от того факта, что существует n ^ 2 уникальных способов обработки графа с помощью алгоритма Крускала? Я имею в виду, что если есть только 3 уникальных способа для алгоритма Крускала обработать граф с 10 узлами, повторение процесса n ^ 2 раза не даст n ^ 2 уникальных «последних ребер». Как это будет работать в сценарии, где имеется менее n^2 уникальных финальных срезов (, то есть менее n^2 уникальных «последних ребер» )?

• Что делать, если всего ребер меньше, чем n^2? Например, у вас может быть связный граф из 10 узлов только с 9 ребрами, что означает, что независимо от того, сколько раз вы повторяете алгоритм, у вас не будет n ^ 2 уникальных «последних ребер». Как это будет работать в этой ситуации?

• Не проще ли просто перебрать каждое ребро и проверить, является ли ребро минимальным разрезом? В графе из n узлов максимальное количество уникальных ребер равно n + n -1 + n -2... + 1 ребер, что меньше n^2. И учитывая, что n ^ 2 меньше, чем n ^ 2 log n, почему бы просто не перебрать все ребра, так как это быстрее?