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

Оцените сверху матожидание числа «больших» разрезов (разрезов, больше чем
<m>\frac{n^2}{c}</m>, где с<8), в случайных графах из n вершин с вероятностью зарождения ребра — ½.

;Hint: Сначала надо правильно решить [[MAX-CUT: вероятностное округление/Задачи/Матожидание разреза]].

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