MAX-CUT: вероятностное округление/Задачи/eupce-6-5 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{проверено|}} Покажите, что в графе с n вершинами и m ребрами, существует разрез, размера к…») |
StasFomin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 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).