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

Материал из DISCOPAL
Перейти к: навигация, поиск
м (StasFomin переименовал страницу MAX-CUT: вероятностное округление/Матожидание разреза/Решение в [[MAX-CUT: вероятностное округление/Задачи/Матож…)
 
(не показана одна промежуточная версия этого же участника)
Строка 1: Строка 1:
 +
* [[MAX-CUT: вероятностное округление/Задачи/Матожидание разреза]]
 +
 
Простое решение:
 
Простое решение:
  
Строка 11: Строка 13:
 
[[File:Матожидание разреза в случайном графе.jpg|center]]
 
[[File:Матожидание разреза в случайном графе.jpg|center]]
  
[[Category:Решения]]
+
[[Категория:Решения]]

Текущая версия на 19:15, 6 октября 2020

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

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

→ n²/8

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

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