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