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

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

Цыганова Светлана, 974гр.

Задача Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.

Решение

1) Клика -> упаковка. Пусть у нас задан граф на n вершинах, на котором необходимо найти максимальную клику. Сведем задачу к задаче нахождения максимального числа попарно несересекающихся множеств. Для этого воспользуемся тем фактом, что множество вершин независимо тогда и только тогда, когда оно является кликой в дополнении графа. Тогда будем действовать по следующему алгоритму:

a) Построим дополнение к исходному графу (Это займет полиномиальное время, например, самый простой способ займет ).

б) Найдем на графе-дополнении максимальное число попарно непересающихся подмножеств на, где каждое подмножество обозначается отдельной вершиной. Если какие-то два подмножества пересекаются, это значит, что они соединены ребром на графе.

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

2) Упаковка -> клика.

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

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

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