45
правок
Изменения
Нет описания правки
* <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/>Покажем теперь, что такой граф будет (n+1)-раскрашиваемым тогда и только тогда, когда исходная формула принадлежала 3CNFSAT.
