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

Question

Мы уже видели, что покрывающие деревья и срезы тесно связаны. Вот еще одна связь. Давайте удалим последнее ребро, которое алгоритм Крускала добавляет в связующее дерево; это разбивает дерево на две составляющие, таким образом определяя разрез (S,S) в графе. Что мы можем сказать об этом разрезе? Предположим, что график, с которым мы работали, был невзвешенным, и что его ребра были упорядочены случайным образом равномерно для алгоритма Крускала для их обработки. Вот замечательный факт: с вероятностью, по крайней мере, 1/n^2, (S,S) - минимальный разрез на графике, где размер разреза (S,S) - это количество ребер, пересекающих S и S Это означает, что повторение процесса O(n^2) раз и выдача наименьшего найденного среза дает минимальный срез в G с высокой вероятностью: алгоритм O(mn^2 log n) для невзвешенных минимальных срезов. Некоторая дальнейшая настройка дает алгоритм минимального сокращения O(n^2 log n), изобретенный Дэвидом Каргером, который является самым быстрым известным алгоритмом для этой важной проблемы.

• Не зависит ли это от того факта, что существует 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, почему бы просто не пройти через все ребра, так как это быстрее?

Answer 1

Я думаю, что вы можете неправильно истолковывать, как работает алгоритм. Алгоритм работает, выполняя алгоритм Крускала, пока не будет добавлено последнее ребро, а затем остановлено прямо перед этим. Алгоритм не пытается создать коллекцию этих "последних ребер"; вместо этого, многократно запускается O (n²) случайных итераций алгоритма Крускала для создания O (n²) возможных сокращений. Взятие наименьшего среза среди всех этих возможных срезов дает минимальный срез с высокой вероятностью. Другими словами, не имеет значения, если существует меньше чем O (n²) ребер. Важным является разрез, который остается в конце, а не последний край, который был рассмотрен.

Надеюсь это поможет!