Участник:StasFomin/Решения задач/MAX-CUT: вероятностное округление/Задачи/Матожидание разреза — различия между версиями

Версия 19:12, 6 октября 2020

Простое решение:

• ½·n² ребер в полном графе
• × ½ — вероятность появления ребра
• × ½ — вероятность, что ребро ляжет на разрез.

→ n²/8

Можно длинно и научно (todo — попробовать вычислить это через sympy или Maxima).