10
правок
Изменения
Нет описания правки
Для вероятности <tex>p</tex> того, что функция <tex>\mathrm{getCut}</tex> после своего выполнения получит стянутый граф <tex>G'</tex> соответствующий конкретному разрезу <tex>\langle A, B \rangle</tex> исходного графа <tex>G</tex> верна следующая оценка снизу {{---}} <tex>p(\langle A, B \rangle) \geqslant</tex> <tex dpi="150">\frac{2}{n^2}</tex>.
|proof =
По [[#Лемма4|лемме 4]] искомый стянутый граф будет получен тогда и только тогда, когда ни одно из ребер разреза не будет стянуто. Так как на каждой итерации алгоритма мы случайно выбираем ребро для стягивания, то можно оценить вероятность того, что ни одно из ребер разреза не будет стянуто. Каждое стягивание уменьшает количество ребер на <tex>1</tex>. Таким образом после <tex>i</tex>-ой итерации алгоритма количество вершин в текущем графе будет равно <tex>n - i + 1</tex>. Рассчитаем вероятность того, что на <tex>i</tex>-ой итерации будет стянуто ребро из разреза <tex>\langle A, B \rangle</tex>. Пусть <tex>w = w(A, B)</tex>. По [[#Лемма2|лемме 2]] величина минимального потока в текущем графе будет на не меньше, чем <tex>w</tex>, и в нем будет не менее <tex dpi="150">\frac{w(n-i+1)}{2}</tex> вершин по [[#Лемма3|лемме 3]]. Тогда вероятность того, что будет стянуто ребро из разреза <tex>\langle A, B \rangle</tex>, при условии, что до этого не было стянуто ни одно из ребер разреза, будет не более
<tex dpi="150">\frac{2\cdot w(A,B)}{w\cdot (n-i+1)}=\frac{2}{n-i+1}.</tex>
