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