10
правок
Изменения
Нет описания правки
'''Стягиванием''' (англ. ''contraction'') ребра <tex>uv</tex> назовем следующую последовательность действий:
# Добавляем новую вершину <tex>w</tex>.
# Для всех ребер <tex>xu</tex> и <tex>xv</tex> (где <tex>x \in V, x \neq v, x \neq u</tex>) добавляем новые ребра <tex>xw</tex>. При этом, если получаются кратные ребра {{- --}} оставляем их.
# Удаляем вершины <tex>u</tex> и <tex>v</tex> и все инцидентные им ребра.
}}
|definition=
'''Разрезом''' (англ. ''cut'') <tex>\langle A, B \rangle</tex> называется разбиение множества <tex>V</tex> на два множества <tex>A</tex> и <tex>B</tex>, удовлетворяющее следующим условиям:
* <tex>A, B \subset V</tex>;,* <tex>A, B \neq \emptyset</tex>;,* <tex>A \cap B = \emptyset</tex>;,
* <tex>A \cup B = V</tex>.
}}
|about = 3
|id = Лемма3
|statement = Пусть <tex>c</tex> {{---}} вес минимального потока в графе <tex>G</tex>. Тогда <tex>m \geq geqslant nc/2</tex>.
|proof =
Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем <tex>c</tex>. Действительно, пусть <tex>\deg(v) < c</tex> для некоторой вершины <tex>v \in V</tex>. Тогда <tex>w(v, G \setminus v) = \deg(v) < c</tex>, что противоречит условию. Далее, по [[Лемма_о_рукопожатиях|лемме о рукопожатиях]] имеем, что <tex>m \geq geqslant nc/2</tex>. Лемма доказана.
}}
{{Теорема
|statement =
Для вероятности <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) \geqgeqslant</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>\xi_i</tex> событие, что на <tex>i</tex>-ой итерации случайным образом будет выбрано ребро из разреза <tex>\langle A, B \rangle</tex>. Тогда мы только что установили, что
<tex dpi="140">p(\xi_i | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) \leq leqslant \frac{2}{n-i+1}.</tex>
<tex dpi="140">p(\overline{\xi_i} | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) = 1 - p(\xi_i | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) \geq geqslant 1 - \frac{2}{n-i+1} = \frac{n-i-1}{n-i+1}.</tex>
Тогда вероятность того, что во время работы функции не будет стянуто ни одно ребро оценивается следующим образом:
<tex dpi="140">p(\overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{n-2}}) = \prod\limits_{i=1}^{n-2} p(\overline{\xi_i} | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) \geq geqslant </tex>
<tex dpi="140">\geq geqslant \prod\limits_{i=1}^{n-2} \frac{n-i-1}{n-i+1} = \frac{n - 2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} \cdot \ldots \cdot \frac{2}{4} \cdot \frac{1}{3} = \frac{2}{n(n-1)} \geq geqslant \frac{2}{n^2}.</tex>
Теорема доказана.
Для этого воспользуемся следующим неравенством:
<tex> e^x \geq geqslant 1 + x</tex> для любого вещественного <tex>x</tex>.
Вероятность того, что мы не получим правильный ответ после <tex>count</tex> независимых запусков равна
Пусть <tex>count = n^2\ln(n)</tex>. Тогда в силу указанного выше неравенства:
<tex dpi="140">(1-\frac{2}{n^2})^{count} \leq leqslant e^{count \cdot (-\frac{2}{n^2})} = e^{-2 \ln(n)} = \frac{1}{n^2}</tex>.
То есть, если вызвать функцию <tex>\mathrm{getCut}</tex> <tex>n^2\ln(n)</tex> раз, и после каждой итерации запоминать минимум, то вероятность того, что найденный ответ будет неверен <tex> \leq leqslant \frac{1}{n^2}</tex>. Даже при небольших значениях <tex>n</tex> алгоритм практически гарантированно выдает правильный ответ.
== Оценка времени работы алгоритма ==
Это медленнее, чем оригинальный алгоритм, однако вероятность нахождения разреза минимального веса экспоненциально выше. Достаточно запустить алгоритм <tex>c\log^2(n)</tex> раз, где <tex>c</tex> - некоторая константа. Действительно, рассчитаем вероятность неправильного ответа также, как раньше:
<tex dpi="160">(1-\frac{1}{log(n)})^{c\log^2(n)} \leq leqslant e^{c\log^2(n) \cdot -\frac{1}{log(n)}} = \frac{1}{n^c}.</tex>
Итоговое время работы {{---}} <tex> O(n^2\log(n)) \cdot c\log^2(n) = O(n^2\log^3(n))</tex>.
