MAX-CUT: вероятностное округление/Задачи/merge-vertices — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена :Решенные задачи на :Нерешенные задачи) |
StasFomin (обсуждение | вклад) |
||
| Строка 68: | Строка 68: | ||
Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m> | Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m> | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
Версия 08:19, 25 апреля 2019
Минимальный разрез в графе (стягивание вершин)
Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф c вершинами и ребрами.
Алгоритм основан на операции стягивания ребра между двумя вершинами. После стягивания ребра получим новый граф без вершины в котором каждое ребро вида заменено ребром (петли также удаляются). Алгоритм следующий
for i=0 to n-2: выбрать случайное ребро e стянуть ребро e
В конце, «восстанавливаем разрез» — каждая его часть соответствует вершинам, содержащимся в одной из метавершин.
Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью