MAX-CUT: вероятностное округление/Задачи/merge-vertices — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
Давайте разберемся с фразой «легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин»
 
Давайте разберемся с фразой «легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин»
 
Вот пример работы алгоритма:
 
Вот пример работы алгоритма:
 +
 
<neato>
 
<neato>
 
graph G{
 
graph G{
Строка 30: Строка 31:
 
}
 
}
 
</neato>
 
</neato>
 
 
<neato>
 
<neato>
 
graph G{
 
graph G{
Строка 40: Строка 40:
 
}
 
}
 
</neato>
 
</neato>
 
 
<neato>
 
<neato>
 
graph G{
 
graph G{
Строка 48: Строка 47:
 
}
 
}
 
</neato>
 
</neato>
 
 
<neato>
 
<neato>
 
graph G{
 
graph G{

Версия 11:06, 19 декабря 2013

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

Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф c вершинами и ребрами.

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

for i=0 to n-2:
   выбрать случайное ребро e
   стянуть ребро e

По завершению алгоритма легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин.


StasFomin 12:05, 19 декабря 2013 (MSK): Понятно, что упражнение в некотором смысле копипаста отсюда. Давайте разберемся с фразой «легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин» Вот пример работы алгоритма:

[svg] [svg] [svg] [svg]

Вот конец его работы. [svg]

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



Доказать, что вероятностный алгоритм вычисляет мимнимальный разрез с вероятностью