MAX-SAT: вероятностное округление/Задачи/eupce-6-3-a — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{проверено|}} {{eupce-6-3}} Покажите, что каждый S(σ) будет независимым множеством в G. Категор…») |
StasFomin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | {{проверено|}} | + | {{проверено|[[Участник:StasFomin|StasFomin]] 22:42, 17 декабря 2024 (UTC)}} |
{{eupce-6-3}} | {{eupce-6-3}} | ||
Покажите, что каждый S(σ) будет независимым множеством в G. | Покажите, что каждый S(σ) будет независимым множеством в G. | ||
| + | {{reserve-task|[[Участник:Конин Георгий|Конин Георгий]] 10:48, 13 декабря 2024 (UTC)}} | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Текущая версия на 22:42, 17 декабря 2024
Проверено: StasFomin 22:42, 17 декабря 2024 (UTC)
- Дан n-вершинный неориентированный граф G=(V, E).
Рассмотрим следующий метод генерации независимого множества.
Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда ни один сосед j вершины i не предшествует i в перестановке σ.
Покажите, что каждый S(σ) будет независимым множеством в G.
Задача зарезервирована: Конин Георгий 10:48, 13 декабря 2024 (UTC)