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