MAX-CUT: вероятностное округление/Задачи/Матожидание разреза — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 6: | Строка 6: | ||
[[Категория:Решенные задачи]] | [[Категория:Решенные задачи]] | ||
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:50, 4 мая 2023
Рассмотрим случайные графы
- из n вершин,
- ребро возникает между любой парой вершин с вероятностью ½.
Напишите формулу матожидания средней величины разреза по всем таким случайным графам из n-вершин.