Обсуждение:Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Packing=MaxClique — различия между версиями

@@ Строка 1: / Строка 1: @@
-== Решение ==
-Представим каждое подмножество как вершину графа. Переберем все пары подмножеств, и если два подмножества не пересекаются - соединим соответствующие им вершины ребрами. Получаем граф. Максимальный подграф, состоящий из вершин, каждая из которых соединена с каждой (это и есть клика) даст нам максимальный набор подмножеств, не пересекающихся друг с другом.
-:
-:В обратную сторону задача сводится аналогичным образом.
-Для каждой вершины v:
-:1) Проходим по всем вершинам v' != v
-:2) Если v' и v не соединены ребром (множества, соответствующие им, должны пересекаться) - добавляем в соответствующие множества уникальный элемент "v-v'", по которому они будут пересекаться друг с другом и ни с каким больше множеством.
-Сводимость в обратную сторону построена.

Текущая версия на 22:25, 14 июня 2011