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

Материал из DISCOPAL
< MAX-CUT: вероятностное округление‎ | Задачи
Версия от 01:46, 21 декабря 2012; Dima Arkhangelskiy (обсуждение) (Created page with "Минимальный разрез в графе (стягивание вершин) Рассмотрим рандомизированный алгоритм Каргера-...")

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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


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

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