45
правок
Изменения
Нет описания правки
=== Доказательство принадлежности задачи классу NPH ===
Сведем задачу 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> {{&mdash}} ; переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <math> \{x_i\}_{i=1}^n </math>.<br/> Заметим следующие тривиальные факты, которые будут использованы при построении графа:
# Ровно одно выражение из <math> \{x_i, \lnot {x_i}\} </math> истинно;
# <math> \varphi \in 3CNFSAT \Leftrightarrow \forall {j} (a_j \lor b_j \lor c_j) = 1 </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/>
==== Доказательство корректности сведения ====
Покажем теперь, что такой граф будет (n+1)-раскрашиваемым тогда и только тогда, когда исходная формула принадлежала 3CNFSAT.
# <math> \Rightarrow </math>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет c0, а вершины, соответствующие ложным термам, - — в соответствующие "ложные" цвета.
# <math> \Leftarrow </math>. Построим по раскраске графа набор переменных <math> \{x_i\}_{i=1}^n </math>, в котором <math> x_i </math> истинно тогда и только тогда, когда <math> v_i </math> покрашена в цвет <math> c_0 </math>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истину, так как по постронию в каждой скобке есть хотя бы один истинный терм.
