MAX-CUT: вероятностное округление/Задачи/Матожидание разреза — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) м (StasFomin переименовал страницу MAX-CUT: вероятностное округление/Матожидание разреза в [[MAX-CUT: вероятностное округление/Задачи/Матожидание р…) |
|||
(не показана одна промежуточная версия этого же участника) | |||
Строка 5: | Строка 5: | ||
Напишите формулу матожидания средней величины разреза по всем таким случайным графам из <tt>n</tt>-вершин. | Напишите формулу матожидания средней величины разреза по всем таким случайным графам из <tt>n</tt>-вершин. | ||
− | [[ | + | [[Категория:Решенные задачи]] |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + |
Версия 19:12, 6 октября 2020
Рассмотрим случайные графы
- из n вершин,
- ребро возникает между любой парой вершин с вероятностью ½.
Напишите формулу матожидания средней величины разреза по всем таким случайным графам из n-вершин.