45
правок
Изменения
Нет описания правки
Сведем задачу 3CNFSAT к данной.<br/>
Пусть дана <math> \varphi = (a_1 \lor b_1 \lor c_1) \land (a_2 \lor b_2 \lor c_2) \land ... \land (a_m \lor b_m \lor c_m) </math>, где <math>a_i</math>, <math>b_i</math> и <math>c_i</math> - переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <math> \{x_i\}_{i=1}^n </math>.<br/> Заметим следующие тривиальные факты, которые будут использованы при построении графа:
Построим множества V и E будущего графа следущим образом:
* <math> V = \{c_j\}_{j=0}^m </math>;
* <math> E = \{<c_i, c_j>\}_{i,j=0, i \ne j}^m </math>;
Будем интерпретировать <math> c_i </math> как цвет, причем <math>c_0</math> - цвет, обозначающий истину.
* <math> \forall i \in \{1 .. n\} </math> добавим в V вершины <math> v_i, \tilde{v_i}\}_{i=1}^n </math>, отвечающие <math> x_i </math> и <math> \lnot {x_i} </math> соответственно;* <math> \forall i \in \{1 .. n\} </math> соединим каждую вершину из <math> \{v_i, \tilde{v_i}\} </math> со всеми <math> c_j </math>, кроме <math> c_0 </math> и <math> c_i </math>. Этим мы обеспечили выполнение первого условия из приведенных выше.<br/>Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет <math> c_0 </math>.
