Изменения
Нет описания правки
{{Определение
|definition=
'''Стянутым графом''' (англ. ''contracted graph'') называется граф, состоящий из двух мультивершинили одной мультивершины и одной обычной вершины (которую, чтобы избежать оговорок в дальнейшем, также будем называть мультивершиной), полученный из исходного графа последовательным стягиванием произвольных ребер.
}}
}}
Задача поиска разреза минимальной веса (англ. ''min-cut problem'') заключается в поиске разреза минимального веса среди всех возможных разрезов исходного графа. Эту задачу можно решить с помощью любого из алгоритмов поиска максимального потока, зафиксировав произвольную вершину <tex>s</tex> в качестве истока и запуская его <tex>O(n)</tex> раз для всех возможных стоков. Если использовать быстрый алгоритм поиска максимального потока, работающий за <tex>O(mn)</tex>, то время работы такого алгоритма поиска минимального разреза будет <tex>O(n^2m)</tex>. Однако ниже Ниже описан существенно более простой в реализации и более быстрый сравнимый по скорости алгоритм Каргера. При некоторых оптимизациях, этот алгоритм работает значительно быстрее, чем использование алгоритмов поиска максимального потока.
== Алгоритм ==
|proof =
Необходимость:. От противного. Если некоторое ребро <tex>uv</tex>, принадлежащее разрезу <tex>\langle A, B \rangle</tex> в <tex>G</tex> будет стянуто, то обе вершины <tex>u</tex> и <tex>v</tex> будут принадлежать одной мультивершине, а значит <tex>G'</tex> не соответствует разрезу <tex>\langle A, B \rangle</tex>. Противоречие.
Достаточность:. Пусть ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex> не было стянуто. Рассмотри Рассмотрим произвольную пару вершин <tex>u \in A</tex> и <tex>v \in B</tex> в графе <tex>G</tex>. Если алгоритм стянул <tex>u</tex> и <tex>v</tex> в одну мультивершину в <tex>G'</tex>, тогда по [[Алгоритм Каргера #лемма1|лемме 1]] существует путь <tex>p</tex> между вершинами <tex>u</tex> и <tex>v</tex>, и все ребра этого пути были стянуты. Но <tex>p</tex> пересекает разрез <tex>\langle A, B \rangle</tex>, что противоречит предположению, что ни одно ребро не было стянуто. Значит, вершины из любой пары <tex>u \in A</tex>, и <tex>v \in B</tex> были стянуты в разные мультивершины. А так, как стянутый граф состоит только из двух мультивершин, значит одна из них была получена стягиванием всех вершин из <tex>A</tex>, а другая {{---}} из <tex>B</tex>. Лемма доказана.}} {{Теорема|statement =Для вероятности <tex>p</tex> того, что функция <tex>getCut</tex> после своего выполнения получит стянутый граф <tex>G'</tex> соответствующий конкретному разрезу <tex>\langle A, B \rangle</tex> исходного графа <tex>G</tex> верна следующая оценка снизу {{---}} <tex>p(\langle A, B \rangle) \geq</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>. По [[#Лемма1Лемма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>
Обозначим за <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 \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 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 </tex>
<tex dpi="140">\geq \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 \frac{2}{n^2}.</tex>
Теорема доказана.
}}
Таким образом, мы получили, что вероятность получить правильный ответ после единичного запуска функции <tex>getCut</tex> очень мала. Однако, вызвав эту функцию <tex>c</tex> раз мы увеличим эту вероятность. Рассчитаем значен <tex>c</tex>, чтобы вероятность успеха была близка к <tex>1</tex>.
Для этого воспользуемся следующим неравенством:
<tex> e^x \geq 1 + x</tex> для любого вещественного <tex>x</tex>.
Вероятность того, что мы не получим правильный ответ после <tex>c</tex> независимых запусков равна
<tex dpi="140">(1-\frac{2}{n^2})^c</tex>.
Пусть <tex>c = n^2ln(n)</tex>. Тогда в силу указанного выше неравенства:
<tex dpi="140">(1-\frac{2}{n^2})^c \leq e^{c \cdot (-\frac{2}{n^2})} = e^{-2ln(n)} = \frac{1}{n^2}</tex>.
То есть, если вызвать функцию <tex>getCut</tex> <tex>n^2\ln(n)</tex> раз, и после каждой итерации запоминать минимум, то вероятность того, что найденный ответ будет неверен <tex> \leq \frac{1}{n^2}</tex>. Даже при небольших значениях <tex>n</tex> алгоритм практически гарантированно выдает правильный ответ.
== Оценка времени работы алгоритма ==
Время работы функции <tex>getCut</tex> {{---}} <tex>O(n^2)</tex>. Функция работает <tex>O(n^2\log(n))</tex> раз. Итоговое время работы {{---}} <tex>O(n^4 \log(n))</tex>.
== Оптимизация алгоритма ==
Каргер совместно со Штейном (англ. ''Stein'') придумали оптимизацию алгоритма Каргера, значительно ускоряющую время его работы. Новый алгоритм называется в честь обоих создателей {{---}} алгоритм Каргера-Штейна (англ. ''Karger-Stein algorithm''). Его суть заключается в следуюшем. Заметим, что вероятность стягивания вершины, принадлежащей минимальному разрезу, в начале выполнения функции <tex>getCut</tex> довольна мала, в то время, как вероятность стянуть ребро, которое не следует стягивать, ближе к концу работы функции существенно возрастает. Тогда будем использовать следующую рекурсивную версию алгоритма:
# Запускаем функцию <tex>getCut</tex> и стягиваем ребра до тех пор, пока не останется <tex>\frac{n}{\sqrt{2}}</tex> вершин.
# Запускаем независимо эту же функцию для получившегося графа дважды и возвращаем минимальный из ответов.
Такая модификация алгоритма выдает правильный ответ с точностью, не менее <tex>\frac{1}{\log(n)}</tex>. Время работы функции <tex>getCut</tex> вычисляется рекурсивной функцией:
<tex>T(n) = O(n^2) + T(n/\sqrt{2}) = O(n^2\log(n))</tex>.
Это медленнее, чем оригинальный алгоритм, однако вероятность нахождения разреза минимального веса экспоненциально выше. Достаточно запустить алгоритм <tex>c\log^2(n)</tex>, где <tex>c</tex> - некоторая константа. Действительно, рассчитаем вероятность неправильного ответа также, как раньше:
<tex dpi="160">(1-\frac{1}{log(n)})^{c\log^2(n)} \leq 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>.
== Источники ==
* Jon Kleinberg, Éva Tardos. Algorithm Design, section 13.2. Min-Cut and Randomization.
* [http://en.wikipedia.org/wiki/Karger's_algorithm Karger's algorithm — Wikipedia]
* [http://nickhar.wordpress.com/2012/02/06/lecture-10-minimum-cuts-by-the-contraction-algorithm/ Lecture notes for CPSC 536N "Randomized Algorithms"]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
