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