Изменения

'''Алгоритм Каргера''' (англ. ''Karger's algorithm'') {{---}} рандомизированный алгоритм для нахождения минимального разреза в связном графе. Он был разработан Дэвидом Каргером (англ. ''David Karger'') в 1993 году.

Пусть <tex>G</tex> {{---}} неориентированный [[Основные_определения_теории_графов#def1 | мультиграф ]] с множеством вершин <tex>V</tex> и множеством ребер <tex>E</tex>, и <tex>|V| = n</tex>, <tex>|E| = m</tex>.

# Для всех ребер <tex>xu</tex> и <tex>xv</tex> (где <tex>x \in V, x \neq v, x \neq u</tex>) добавляем новые ребра <tex>xw</tex>. При этом, если получаются кратные ребра {{- --}} оставляем их.

* <tex>A, B \subset V</tex>;,* <tex>A, B \neq \emptyset</tex>;,* <tex>A \cap B = \emptyset</tex>;,

Пусть нам дан граф <tex>G = \{V, E\}</tex>. <code> '''int''' minCut(G): answer = INF;<tex>\infty</tex> '''for ''' i = 1..c'''to''' count curCut = getCut(G); '''if ''' curCut < answer answer = curCut; '''return ''' answer;</code>Так как алгоритм вероятностный и функция <tex>\mathrm{getCut}</tex> возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию <tex>ccount</tex> раз. Какое конкретное значение <tex>ccount</tex> выбрать будет описано ниже.Реализация функции <tex>\mathrm{getCut}</tex> {{---}} это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа. <code> '''int''' getCut(graph): n G = graph vertexCount = количество вершин в G; '''while n ''' vertexCount > 2 e edge = случайное ребро из G; contract(eedge);<font color="darkgreen">//стягиваем ребро edge</font> nvertexCount--; m edgeCount = количество ребер в G; '''return m;''' edgeCount</code>

Докажем корректность алгоритма. Для удобства доказательства и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция <tex>\mathrm{getCut}</tex> вернет правильный вес, но посчитает его на другом минимальном разрезе, то будем считать, что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.

Рассмотрим подграф <tex>G'</tex> исходного графа <tex>G</tex> в который входят все ребра, которые были стянуты в вершину <tex>w</tex>. Очевидно, что <tex>G'</tex> связен, а значит в нем существует путь между его любыми двумя вершинавершинами. Следовательно, существует путь между <tex>u</tex> и <tex>v</tex>, состоящий из стянутых ребер. Лемма доказана.

|statement = Пусть <tex>c</tex> {{---}} вес минимального потока в графе <tex>G</tex>. Тогда <tex>m \geq geqslant nc/2</tex>.

Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем <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>\mathrm{getCut}</tex> после своего выполнения получит стянутый граф <tex>G'</tex> соответствующий конкретному разрезу <tex>\langle A, B \rangle</tex> исходного графа <tex>G</tex> тогда и только тогда, когда ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex>, не будет стянуто.

Для вероятности <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>.

По [[#Лемма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="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>\mathrm{getCut}</tex> очень мала. Однако, вызвав эту функцию <tex>ccount</tex> раз мы увеличим эту вероятность. Рассчитаем значение <tex>ccount</tex> такое, чтобы вероятность успеха была близка к <tex>1</tex>.

<tex> e^x \geq geqslant 1 + x</tex> для любого вещественного <tex>x</tex>.

Вероятность того, что мы не получим правильный ответ после <tex>ccount</tex> независимых запусков равна

Пусть <tex>c count = n^2ln2\ln(n)</tex>. Тогда в силу указанного выше неравенства:

<tex dpi="140">(1-\frac{2}{n^2})^c {count} \leq leqslant e^{c count \cdot (-\frac{2}{n^2})} = e^{-2ln2 \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>\mathrm{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>\mathrm{getCut}</tex> довольна довольно мала, в то время, как вероятность стянуть ребро, которое не следует стягивать, ближе к концу работы функции существенно возрастает. Тогда будем использовать следующую рекурсивную версию алгоритма:# Запускаем функцию <tex>\mathrm{getCut}</tex> и стягиваем ребра до тех пор, пока не останется <tex>\frac{n}{\sqrt{2}}</tex> вершин.

Такая модификация алгоритма выдает правильный ответ с точностью, не менее <tex>\frac{1}{\log(n)}</tex>. Время работы функции <tex>\mathrm{getCut}</tex> вычисляется рекурсивной функцией:

<tex>T(n) = O(n^2) + 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 leqslant e^{c\log^2(n) \cdot -\frac{1}{log(n)}} = \frac{1}{n^c}.</tex>