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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Created page with "Минимальный разрез в графе (стягивание вершин) Рассмотрим рандомизированный алгоритм Каргера-...")
 
Строка 1: Строка 1:
 
Минимальный разрез в графе (стягивание вершин)
 
Минимальный разрез в графе (стягивание вершин)
  
−
Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф <m>G=(V, E)</m> c <m>n</m> вершинами и <m>m</m> ребрами. Алгоритм основан на операции стягивания ребра между двумя вершинами. После стягивания ребра <m>(u, v)</m> получим новый граф без вершины <m>v</m> в котором каждое ребро вида <m>(v, x)</m> заменено ребром <m>(u, x)</m>(петли также удаляются).
+
Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф <m>G=(V, E)</m> c <m>n</m> вершинами и <m>m</m> ребрами.  
 +
 
 +
Алгоритм основан на операции стягивания ребра между двумя вершинами. После стягивания ребра <m>(u, v)</m> получим новый граф без вершины <m>v</m> в котором каждое ребро вида <m>(v, x)</m> заменено ребром <m>(u, x)</m>(петли также удаляются).
 
Алгоритм следующий
 
Алгоритм следующий
 +
 
<code-python>
 
<code-python>
−
for i = 0 to n - 2
+
for i=0 to n-2:
−
выбрать случайное ребро e
+
  выбрать случайное ребро e
−
стянуть ребро 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>
 +
graph G{
 +
1--2
 +
2--3
 +
3--4
 +
4--1
 +
3--1
 +
4--2
 +
2--5
 +
3--5
 +
}
 +
</neato>
 +
 +
<neato>
 +
graph G{
 +
12--3
 +
3--4
 +
4--12
 +
12--5
 +
3--5
 +
}
 +
</neato>
 +
 +
<neato>
 +
graph G{
 +
12--34
 +
12--5
 +
34--5
 +
}
 +
</neato>
 +
 +
<neato>
 +
graph G{
 +
1234--5
 +
}
 +
</neato>
 +
 +
Вот конец его работы.
 +
<neato>
 +
graph G{
 +
12345
 +
}
 +
</neato>
 +
 +
Теперь — покажите, как ««легко указать минимальный разрез в графе».
 +
[[Category:Проблемы в решении]]
 +
----
  
  
−
По завершению алгоритма легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин.
 
  
 
Доказать, что вероятностный алгоритм вычисляет мимнимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m>
 
Доказать, что вероятностный алгоритм вычисляет мимнимальный разрез с вероятностью <m>P \ge \frac{2}{n(n-1)}</m>
  
 
[[Category:Предложенные студентами задачи]]
 
[[Category:Предложенные студентами задачи]]

Версия 08:05, 19 декабря 2013

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

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

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

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

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

StasFomin 12:05, 19 декабря 2013 (MSK): Понятно, что упражнение в некотором смысле копипаста отсюда. Давайте разберемся с фразой «легко указать минимальный разрез в графе: каждая его часть соответствует вершинам, содержащимся в одной из метавершин» Вот пример работы алгоритма: [svg]

[svg]

[svg]

[svg]

Вот конец его работы. [svg]

Теперь — покажите, как ««легко указать минимальный разрез в графе».


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

Источник — «https://discopal.ispras.ru/index.php?title=MAX-CUT:_вероятностное_округление/Задачи/merge-vertices&oldid=2487»