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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Created page with "Пусть минимальный разрез <m>C</m> состоит из <m>k</m> ребер. Тогда все вершины имеют степень не меньше <...")
 
(нет различий)

Текущая версия на 01:50, 21 декабря 2012

Пусть минимальный разрез состоит из ребер. Тогда все вершины имеют степень не меньше (Если бы какая-нибудь вершина имела степень меньше , то разрез состоял бы менее чем из ребер, противоречие). Поскольку каждое ребро учитывается при подсчете степеней обоих вершин, а суммарная степень вершин не меньше , то граф должен содержать хотя бы ребер. Событие : "стянутое на итерации ребро не входит в минимальный разрез ". Требуется оценить вероятность успеха .

Заметим, что . Оценим вероятности всех сомножителей и подставим значения.

Рассмотрим первую итерацию. По крайней мере из ребер входят в минимальный разрез .

Вероятность ошибки на первой итерации не превосходит . Следовательно для успеха на первой итерации справедлива оценка:

.


В результате стягивания ребра на первой итерации число вершин уменьшилось на одну, тем не менее, осталось хотя бы ребер. На второй итерации получаем:


.


Для остальных вершин вероятности успеха:

.


В результате, когда алгоритм завершит работу, вероятность нахождения минимального разреза составит: