Задача и клике.

Задача формулируется так: содержит ли данный граф G k – клику, где k – целое число. На вход алгоритма подается цепочка

k (x ₁ ,y₁) …(x _m ,y _m), где (x _i ,y _i ) – ребра m - узельного графа G, задаваемые номерами своих вершин. Задача о клике принадлежит классу NP. Недетерминированная машина Тьюринга “догадывается”, какие k вершин составляют полный подграф, а затем это проверяется, для чего достаточно O(n³) шагов, где n - длина кода задачи о клике.

Теорема.Задача ВКНФ полиномиально сводится к задаче о клике. Поэтому задача о клике NP – полна.

Доказательство. Пусть F = F₁…F _q - формула в КНФ, где F_i = Ú x _{i j} ,

j=1,…,k _i

x _{i j} - литерал. Построим неориентированный граф G = (V, E), узлы кото- рого представляются парами целых чисел [ i, j ] для 1£ i £ q, 1£j£ k_i .

Первое число i обозначает член F_i , второе j - литерал, входящий в F_i , т.е. x _{i j} . Таким образом, каждый узел графа естественным образом соответствует вхождению в конкретный сомножитель.

Ребра образуют пары [ i, j ], [ k, s], для которых i ¹ k и x _{i j} ¹ Øx _{k s} .

Присвоение смежным вершинам значения 1 превращает в истину оба члена - F_i и F _k .

Число узлов в G, очевидно, меньше длины формулы F, а число ребер не превосходит квадрата числа узлов. Граф G можно закодировать цепочкой, длина которой ограничена полиномом от длины формулы F, а найти такой код можно за время, ограниченное полиномом от длины F.

Покажем, что граф G содержит q-клику тогда и только тогда, когда формула F выполнима.

Достаточность. Пусть формула F выполнима. Тогда на некотором наборе из 0 и 1 формула F обращается в 1. Поскольку на этом наборе каждый сомножитель F_i обращается в 1, то в каждом сомножителе найдется литерал, принимающий значение 1, который обозначим как x _{i m i} . Покажем, что множество узлов {[ i, m _i ]: 1£ i £ q } образует q –клику.

В противном случае нашлись бы такие i и j , что i ¹ j и вершины

[ i, m _i ], [ j, m _j ] не смежные. Из приведенного выше построения графа по формуле F следует, что x _{i m i} = Øx_{j m j} , что невозможно, так как

x _{i m i} = x_{j m j} = 1.

Необходимость. Пусть G содержит q-клику. Первые компоненты узлов, составляющих клику, должны быть различны. Так как в q-клике q узлов, то узлы клики взаимно однозначно соответствуют сомножителям формулы F.

Пусть S₁ = {y:x _{i m i} = y, где 1£ i £ q }, S₂ = {y:x _{i m i} = Øy, где 1£ i £ q }, тогда S₁ Ç S₂ = Æ, ибо в противном случае какие-то узлы [ i, m _i ] и

[ j, m _j ], для которых x _{i m i} = Ø x _{j m j} , соединялись бы ребром. Если положить переменные из S₁ равными 1, а из S₂ равными 0, то каждая формула F_i примет значение 1, т.е. формула F выполнима.

Пример. На рис. 10.7 представлен граф, построенный по предложенному выше алгоритму на основании формулы F= (y₁ + Øy ₂)(y₂ + Øy₃)( y₃ + Øy₁), где литералы соответственно представлены:

x₁₁ = y₁ , x₂₁ = y₂ , x₃₁ = y₃ ,

x₁₂ = Øy₂ , x₂₂ = Øy₃ , x₃₂ = Øy₁ .

Три сомножителя 2-КНФ F показывают, что граф на рис. 10.7 содержит две 3-клики: {[1,1], [2,1], [3,1]} и {[1,2], [2,2], [3,2]}. Литералы первой клики выполняют F при y₁ = y₂ = y₃ =1, второй - при y₁ = y₂ = y₃ =0. “

Рис.10.7.