MAX-CUT: вероятностное округление/Задачи/eupce-6-5 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{проверено|}} Покажите, что в графе с n вершинами и m ребрами, существует разрез, размера к…») |
Bruks (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | {{проверено|}} | + | {{reserve-task|[[Участник:Bruks|Bruks]] 20:27, 23 мая 2023 (UTC)}}{{проверено|}} |
Покажите, что в графе с n вершинами и m ребрами, существует разрез, размера как минимум mn/(2n-1). | Покажите, что в графе с n вершинами и m ребрами, существует разрез, размера как минимум mn/(2n-1). | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Версия 20:27, 23 мая 2023
Задача зарезервирована: Bruks 20:27, 23 мая 2023 (UTC)
Покажите, что в графе с n вершинами и m ребрами, существует разрез, размера как минимум mn/(2n-1).