MAX-CUT: вероятностное округление/Задачи/0.5-приближенный вероятностный для MAX-CUT — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 15 промежуточных версий этого же участника)
Строка 1: Строка 1:
−
 
−
===== Задача «0.5-приближенный вероятностный для MAX-CUT» =====
 
 
<latex>
 
<latex>
−
 
 
Для задачи о поиске максимального разреза в простом, невзвешенном графе можно применить простую стратегию:
 
Для задачи о поиске максимального разреза в простом, невзвешенном графе можно применить простую стратегию:
 
каждую вершину равновероятно ($p=1/2$) приписать к~множеству $T$ или $S$.
 
каждую вершину равновероятно ($p=1/2$) приписать к~множеству $T$ или $S$.
Строка 9: Строка 6:
 
</latex>
 
</latex>
  
−
[[Категория:На проверку]]
+
[[Категория:Решенные задачи]]
−
 
+
−
===Стенина Мария, группа 974===
+
−
 
+
−
<latex>
+
−
Обозначим максимально возможный размер разреза $R^*$, а размер разреза, полученный рандомизированным алгоритмом, $R$. Найдем математическое ожидание $\mathbb{E} R$. Каждое ребро попадает в разрез с вероятностью 0.5, потому что при описанном способе отнесения вершин к одной из частей графа вероятность того, что обе вершины, инцидентные ребру, окажутся по разные стороны разреза, равна 0.5. Поэтому ожидание числа ребер в разрезе
+
−
$$
+
−
    \mathbb{E} R = \frac{1}{2} |E| \geq \frac{1}{2} R^*,
+
−
$$
+
−
что и требовалось доказать.
+
−
</latex>
+

Версия 15:49, 20 мая 2020

Источник — «https://discopal.ispras.ru/index.php?title=MAX-CUT:_вероятностное_округление/Задачи/0.5-приближенный_вероятностный_для_MAX-CUT&oldid=10984»