MAX-SAT: вероятностное округление/Задачи/eupce-6-3-b — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 15: | Строка 15: | ||
S(\sigma) = \sum_{i=1}^{n} \frac{1}{d_i + 1} | S(\sigma) = \sum_{i=1}^{n} \frac{1}{d_i + 1} | ||
</m> | </m> | ||
| + | {{reserve-task|[[Участник:Конин Георгий|Конин Георгий]] 10:49, 13 декабря 2024 (UTC)}} | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Версия 10:49, 13 декабря 2024
- Дан n-вершинный неориентированный граф G=(V, E).
Рассмотрим следующий метод генерации независимого множества.
Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда ни один сосед j вершины i не предшествует i в перестановке σ.
Предложите вероятностный алгоритм для поиска σ для которого можно показать, что ожидаемый размер
где означает степень вершины i.
Докажите, что в G существует независимое множество размера как минимум
Задача зарезервирована: Конин Георгий 10:49, 13 декабря 2024 (UTC)