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