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

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

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

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

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

→ n²/8

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

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