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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
 
(не показано 9 промежуточных версий этого же участника)
(нет различий)

Текущая версия на 18:49, 20 мая 2020

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

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

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

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

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

В конце, «восстанавливаем разрез» — каждая его часть соответствует вершинам, содержащимся в одной из метавершин.

[svg]



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