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

<latex>
Для задачи о поиске максимального разреза в простом, невзвешенном графе можно применить простую стратегию:
каждую вершину равновероятно ($p=1/2$) приписать к~множеству $T$ или $S$.

Докажите, что этот вероятностный алгоритм является $0.5$-приближенным.	
</latex>

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]