MAX-CUT: вероятностное округление/Задачи/merge-vertices — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 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{ | ||
Версия 08:06, 19 декабря 2013
Минимальный разрез в графе (стягивание вершин)
Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф c вершинами и ребрами.
Алгоритм основан на операции стягивания ребра между двумя вершинами. После стягивания ребра получим новый граф без вершины в котором каждое ребро вида заменено ребром (петли также удаляются). Алгоритм следующий
for i=0 to n-2: выбрать случайное ребро e стянуть ребро e
По завершению алгоритма легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин.
StasFomin 12:05, 19 декабря 2013 (MSK): Понятно, что упражнение в некотором смысле копипаста отсюда. Давайте разберемся с фразой «легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин» Вот пример работы алгоритма:
Вот конец его работы.
Теперь — покажите, как ««легко указать минимальный разрез в графе».
Доказать, что вероятностный алгоритм вычисляет мимнимальный разрез с вероятностью