MAX-SAT: вероятностное округление/Задачи/eupce-6-3-a — различия между версиями

Текущая версия на 22:42, 17 декабря 2024

• Дан n-вершинный неориентированный граф G=(V, E).

Рассмотрим следующий метод генерации независимого множества.

Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда ни один сосед j вершины i не предшествует i в перестановке σ.

Покажите, что каждый S(σ) будет независимым множеством в G.