Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/k-подсемейство множеств - NPC

Материал из DISCOPAL
Перейти к: навигация, поиск


Условие.

Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное . Существует ли подсемейство, состоящее из попарно непересекающихся множеств?

Решение.

Сведем задачу о клике к данной задаче.

Пусть дан граф , требуется найти в нем клику размера . Как известно, это NP-полная задача. Рассмотрим теперь граф --- дополнение графа , т.е. граф с тем же множеством вершин, и вершины в нем смежны тогда и только тогда, когда они не смежны в . Пронумеруем ребра графа числами от до , а вершины --- числами от до . Теперь каждой вершине графа поставим в соответствие множество натуральных чисел , в котором хранится, во-первых, номер вершины , а во вторых, номера всех ребер, которые инцидентны вершине .

По построению множества и имеют непустое пересечение тогда и только тогда, когда вершины и смежны в графе . Пусть в семействе множеств существует подсемейство из попарно непересекающихся подмножеств . Тогда в графе вершины попарно несмежны. Тогда в графе вершины попарно смежны, т.е. в графе найдена клика размера .

Таким образом, мы полиномиально (система множеств строится за время ) свели NP-полную задачу о клике к данной задаче. Значит, данная задача NP-полна.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.