Просмотр исходного текста страницы MAX-CUT: вероятностное округление/Задачи/merge-vertices

Минимальный разрез в графе (стягивание вершин)

Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф <m>G=(V, E)</m> c <m>n</m> вершинами и <m>m</m> ребрами. 

Алгоритм основан на операции стягивания ребра между двумя вершинами. После стягивания ребра <m>(u, v)</m> получим новый граф без вершины <m>v</m> в котором каждое ребро вида <m>(v, x)</m> заменено ребром <m>(u, x)</m>(петли также удаляются).
Алгоритм следующий

<code-python>
for i=0 to n-2:
   выбрать случайное ребро e
   стянуть ребро e
</code-python>
По завершению алгоритма легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин.

----
[[Участник:StasFomin|StasFomin]] 12:05, 19 декабря 2013 (MSK):
Понятно, что упражнение в некотором смысле копипаста [http://rain.ifmo.ru/cat/data/theory/graph-circuits-cuts/min-cut-2005/article.pdf отсюда].
Давайте разберемся с фразой «легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин»
Вот пример работы алгоритма:

<neato>
graph G{
1--2
2--3
3--4
4--1
3--1
4--2
2--5
3--5
}
</neato>
<neato>
graph G{
12--3
3--4
4--12
12--5
3--5
}
</neato>
<neato>
graph G{
12--34
12--5
34--5
}
</neato>
<neato>
graph G{
1234--5
}
</neato>

Вот конец его работы.
<neato>
graph G{
12345
}
</neato>

Теперь — покажите, как ««легко указать минимальный разрез в графе».
----


Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m>