Изменения
Нет описания правки
Будем интерпретировать <math> c_i </math> как цвет (соотвественно, вершина <math> c_i </math> всегда покрашена в цвет <math> c_i </math>), причем <math>c_0</math> - цвет, обозначающий истину.
* <math> \forall i \in \{1 .. n\} </math> добавим в V вершины <math> v_i, \tilde{v_i} </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>. Этим мы обеспечили выполнение первого условия из приведенных выше, так как теперь ровно одна вершина из <math> \{v_i, \tilde{v_i}\} </math> окрашена в цвет <math> c_0 </math>, а другая - в цвет <math> c_i </math> <br/>
Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет <math> c_0 </math>.
* Для этого для каждой скобки вида <math> ([\lnot]x_i \lor [\lnot] x_j \lor [\lnot] x_k)_l </math> добавим вершину <math> d_l </math>, соединив ее с соответствующими <math> v_i (\tilde{v_i}), v_j(\tilde{v_j}), v_k(\tilde{v_k}) </math>, а также со всеми <math> c_i </math>, кроме <math> c_i, c_j, c_k </math>. Тем самым, <math> d_l </math> "не дает" покрасить все три вершины, отвечающие термам в скобке, в "ложный" цвет (напомним, что все цвета, кроме <math> c_0 </math> мы условились называть "ложными").<br/>
