45
правок
Изменения
Нет описания правки
# <math> \varphi \in 3CNFSAT \Leftrightarrow \forall {j} (a_j \lor b_j \lor c_j) = 1 </math>
Построим множества V и E будущего графа следущим образом:
* <math> V = \{c_jc_i\}_{ji=0}^m n </math>;* <math> E = \{<c_i, c_j>\}_{i,j=0, i \ne j}^m n </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>.
* Добавим в V вершины <math> \{d_j\}_{j=1}^m </math>, каждую из которых соединим со всеми <math> c_k </math>, кроме тех
