MAX-CUT: вероятностное округление/Задачи/merge-vertices — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
||
| (не показано 18 промежуточных версий этого же участника) | |||
| Строка 11: | Строка 11: | ||
стянуть ребро e | стянуть ребро e | ||
</code-python> | </code-python> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<neato> | <neato> | ||
| Строка 53: | Строка 46: | ||
</neato> | </neato> | ||
| − | + | В конце, «восстанавливаем разрез» — каждая его часть соответствует вершинам, содержащимся в одной из метавершин. | |
| + | |||
<neato> | <neato> | ||
graph G{ | graph G{ | ||
| − | + | 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> | ||
| + | |||
| + | [[Категория:Решенные задачи]] | ||
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:50, 4 мая 2023
Минимальный разрез в графе (стягивание вершин)
Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф c вершинами и ребрами.
Алгоритм основан на операции стягивания ребра между двумя вершинами. После стягивания ребра получим новый граф без вершины в котором каждое ребро вида заменено ребром (петли также удаляются). Алгоритм следующий
for i=0 to n-2: выбрать случайное ребро e стянуть ребро e
В конце, «восстанавливаем разрез» — каждая его часть соответствует вершинам, содержащимся в одной из метавершин.
Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью