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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]])
(не показано 16 промежуточных версий этого же участника)
Строка 11: Строка 11:
 
   стянуть ребро e
 
   стянуть ребро e
 
</code-python>
 
</code-python>
По завершению алгоритма легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин.
 
 
----
 
[[Участник:StasFomin|StasFomin]] 12:05, 19 декабря 2013 (MSK):
 
Понятно, что упражнение в некотором смысле копипаста [http://rain.ifmo.ru/cat/data/theory/graph-circuits-cuts/min-cut-2005/article.pdf отсюда].
 
Давайте разберемся с фразой «легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин»
 
Вот пример работы алгоритма:
 
  
 
<neato>
 
<neato>
Строка 53: Строка 46:
 
</neato>
 
</neato>
  
Вот конец его работы.
+
В конце, «восстанавливаем разрез» — каждая его часть соответствует вершинам, содержащимся в одной из метавершин.
 +
 
 
<neato>
 
<neato>
 
graph G{
 
graph G{
12345
+
1--2
 +
2--3
 +
3--4
 +
4--1
 +
3--1
 +
4--2
 +
 
 +
edge [color=blue]
 +
2--5
 +
3--5
 
}
 
}
 
</neato>
 
</neato>
  
Теперь — покажите, как ««легко указать минимальный разрез в графе».
 
 
----
 
----
  
  
 
Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m>
 
Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m>
 +
 +
[[Категория:Нерешенные задачи]]

Версия 09:08, 20 февраля 2020

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

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

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

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

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

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

[svg]



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