Теорема.Задача о клике полиномиально сводится в задачу об узельном покрытии. Поэтому задача об узельном покрытии NP – полна.
Доказательство. Пусть G=(V, E) – неориентированный граф и Ĝ=(V, Ē) его дополнение, где Ē ={(u,v}ÎV, u ¹ v, (v,u) Ï E}. Покажем, что множество SÍV будет кликой в G тогда и только тогда, когда V\S является узельным покрытием графа Ĝ. Если S –клика в G, то никакое ребро в
Ĝ не соединяет никакие два узла в S. Поэтому любое ребро из Ĝ инцидентно по меньшей мере одному узлу из V\ S, т.е. V\ S есть узельное покрытие графа Ĝ. Аналогично, если V\ S есть узельное покрытие графа Ĝ, то каждое ребро из Ĝ инцидентно по меньшей мере одному узлу из
V\ S. Поэтому никакое ребро из Ĝ не соединяет два узла из S. Следовательно, каждая пара узлов из S соединена в G, и, значит, S – клика в G.
Вопрос полиномиального сведения задачи о k-клики графа G к задаче узельного покрытия размера êV ç- k графа. По данному стандартному представлению графа G и числу k можно найти стандартное представление графа Ĝ и числа êV ç- k за время, полиномиально зависящее от длины представления G и k.
Пример. На рис. 10.8,а граф G содержит две 3-клики {1,2,5} и {1,4,5}.
(две 2-клики {2,3},{3,4}). На рис. 10.8,б граф содержит соответствующие 2-узельные покрытия {3,4} и {2,3} (соответствующие 3-узельные покрытия {1,4,5}, {1,2,5}).
Рис. 10.8.
Задача о сумме подмножеств (SUBSET-SUM).
ЗадачаSUBSET-SUM имеет следующую постановку: существует, ли подмножество S’ Í S, сумма элементов которого равна t.
Например, для S={1, 4, 16, 64, 256, 1040, 1093, 1284, 1344} и t = 3754 ответ положительный, S’ = {1, 16, 64, 256, 1040, 1093, 1284}.
Теорема.Задача SUBSET-SUM является NP-полной.
Доказательство. Задача об узельном покрытии полиномиально сводима к задаче SUBSET-SUM. Сводящий алгоритм преобразует вход < G, k > задачи о вершинном покрытии в пару < S, t > с таким свойством:
в графе G = (V, E) существует вершинное покрытие размера k тогда и только тогда, когда в S найдется подмножество с суммой t.
Будем использовать представление графа G матрицей инцидентности.
Перечислим вершины графа числами 0,…, çV ç - 1, а ребра числами
0,…, çE ç - 1. Тогда матрицей инцидентности графа G будет матрица B, определяемая как: b ij =1, если ребро j инцидентно вершине i, в против- ном случае - b ij = 0. Например, матрица инцидентности на рис. 36.14(б) представляет граф на рис.36.14(а).
Сводящий алгоритм получает на вход матрицу инцидентности B и число k и выдает на входе множество S и число t. Все числа записываются в системе счисления по основанию 4 (рис.36.14(в) ).
Множество S будет состоять из чисел двух типов: одни соответствуют вершинам графа, другие его ребрам. Каждой вершине i Î V ставится в соответствие число, которое записывается так: 1 – первой ячейки и i-я строка матрицы инцидентности. Каждому ребру jÎE сопоставляется число yj , запись которого содержит единственную 1 в j – й позиции (т.е. число 4 j ). Число t имеет коэффициенты 2 во всех младших разрядах и равно числу k по основанию 4 - в старших разрядах, а именно
t = k × 4çE ç + å 2 × 4 j .
j=0,…, çE ç - 1
Рис.36.14.
Все построенные числа имеют двоичное представление полиномиального размера и строятся за полиномиальное время.
Докажем, что граф G имеет k-узельное покрытие тогда и только тогда, когда в S существует подмножество S ‘с суммой t. Пусть V ’ Í V
k-узельное покрытие, содержащее вершины i1 ,…,i k . Включим в множество S‘числа, соответствующие этим вершинам. Тогда сумма элементов множества S‘, записанная по основанию 4, будет выглядеть так: в старших разрядах стоит число k, а во всех младших разрядах стоят цифры 1 или 2 (в зависимости от того, оба конца ребра вошли в вершинное покрытие или только один). Взяв те ребра, у которых только один конец вошел в вершинное покрытие, и добавив соответствующие им числа в множество S’, мы превратим единицы в двойки, т.е. получим в сумме число t. На рис. 36.14,в , чтобы обеспечить 2-ки в младших разрядах, были добавлены строки y0, y2, y3, y4.
Обратное рассуждение аналогично. Пусть имеется множество S’, сумма элементов которого равна t. Это значит, что в младших разрядах суммы t стоят 2-ки. Поскольку строки, соответствующие ребрам, могут дать в каждом разряде максимум 1, это значит, что недостающая 1 приходит от “вершинных” строк. Следовательно, вершины, соответствующие входящим в S’строкам, образуют вершинное покрытие, а старшие разряды указывают, что число вершин в этом покрытии равно k. “
