Участник:StasFomin/Решения задач/MAX-CUT: вероятностное округление/Задачи/Матожидание разреза — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| + | * [[MAX-CUT: вероятностное округление/Задачи/Матожидание разреза]] | ||
| + | |||
Простое решение: | Простое решение: | ||
| Строка 11: | Строка 13: | ||
[[File:Матожидание разреза в случайном графе.jpg|center]] | [[File:Матожидание разреза в случайном графе.jpg|center]] | ||
| − | [[ | + | [[Категория:Решения]] |
Текущая версия на 19:15, 6 октября 2020
Простое решение:
- ½·n² ребер в полном графе
- × ½ — вероятность появления ребра
- × ½ — вероятность, что ребро ляжет на разрез.
→ n²/8
Можно длинно и научно (todo — попробовать вычислить это через sympy или Maxima).
