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

Материал из DISCOPAL
< Участник:StasFomin
Версия от 19:15, 6 октября 2020; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

→ n²/8

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

Матожидание разреза в случайном графе.jpg