45
правок
Изменения
Нет описания правки
* <math> V = \{c_i\}_{i=0}^n </math>;
* <math> E = \{<c_i, c_j>\}_{i,j=0, i \ne j}^n </math>;
Будем интерпретировать <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>.
