Участник:StasFomin/Решения задач/MAX-CUT: вероятностное округление/Задачи/Матожидание разреза
Материал из DISCOPAL
< Участник:StasFomin
Версия от 19:12, 6 октября 2020; StasFomin (обсуждение | вклад) (StasFomin переименовал страницу MAX-CUT: вероятностное округление/Матожидание разреза/Решение в [[MAX-CUT: вероятностное округление/Задачи/Матож…)
Простое решение:
- ½·n² ребер в полном графе
- × ½ — вероятность появления ребра
- × ½ — вероятность, что ребро ляжет на разрез.
→ n²/8
Можно длинно и научно (todo — попробовать вычислить это через sympy или Maxima).
