Изменения
→Орфографическая ошибка
== Оптимизация алгоритма ==
Каргер совместно со Штейном (англ. ''Stein'') придумали оптимизацию алгоритма Каргера, значительно ускоряющую время его работы. Новый алгоритм называется в честь обоих создателей {{---}} алгоритм Каргера-Штейна (англ. ''Karger-Stein algorithm''). Его суть заключается в следуюшем. Заметим, что вероятность стягивания вершины, принадлежащей минимальному разрезу, в начале выполнения функции <tex>\mathrm{getCut}</tex> довольна довольно мала, в то время, как вероятность стянуть ребро, которое не следует стягивать, ближе к концу работы функции существенно возрастает. Тогда будем использовать следующую рекурсивную версию алгоритма:
# Запускаем функцию <tex>\mathrm{getCut}</tex> и стягиваем ребра до тех пор, пока не останется <tex>\frac{n}{\sqrt{2}}</tex> вершин.
# Запускаем независимо эту же функцию для получившегося графа дважды и возвращаем минимальный из ответов.
