Изменения
Нет описания правки
== Доказательство ==
=== Доказательство принадлежности задачи классу NP ===
Сертификатом для решения данной задачи будет последовательность <tex> \{c_i\}_ {i=1}^{n}</tex>, где <tex> n = |V| </tex>, а <tex> c_i </tex> обозначает цвет <tex>i</tex>-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <tex> [1, k] </tex>. С другой стороны, очевидно, что если задача имеет решение, то такой сертификат существует.
=== Доказательство принадлежности задачи классу NPH ===
Сведем задачу [[3CNFSAT]] к данной.<br/>
Построим множества V и E будущего графа следующим образом:
* <tex> V = \{c_i\}_{i=0}^n </tex>;
* <tex> E = \{<\langle c_i, c_j>\rangle \}_{i,j=0, i \ne j}^n </tex>.
Будем интерпретировать <tex> c_i </tex> как цвет (соотвественно, вершина <tex> c_i </tex> всегда покрашена в цвет <tex> c_i </tex>), причем <tex>c_0</tex> — цвет, обозначающий истину, а все остальные цвета означают ложь).
* Для всех <tex> i \in \{1 .. n\} </tex> добавим в V вершины <tex> v_i, \tilde{v_i} </tex>, отвечающие <tex> x_i </tex> и <tex> \lnot {x_i} </tex> соответственно, и соединим каждую такую пару ребром;
* Для этого для каждой скобки вида <tex> ([\lnot]x_i \lor [\lnot] x_j \lor [\lnot] x_k)_l </tex> добавим вершину <tex> d_l </tex>, соединив её с соответствующими <tex> v_i (\tilde{v_i}), v_j(\tilde{v_j}), v_k(\tilde{v_k}) </tex>, а также со всеми <tex> c_i </tex>, кроме <tex> c_i, c_j, c_k </tex>. Тем самым, <tex> d_l </tex> «не даёт» покрасить все три вершины, отвечающие термам в скобке, в «ложный» цвет (напомним, что все цвета, кроме <tex> c_0 </tex>, мы условились называть «ложными»).<br/>
==== Доказательство корректности сведения ====
Покажем теперь, что такой граф будет <tex>(n+1)</tex>-раскрашиваемым тогда и только тогда, когда исходная формула принадлежит 3CNFSAT.# <tex> \Rightarrow </tex>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет <tex>c0</tex>, а вершины, соответствующие ложным термам, — в соответствующие "ложные" цвета.
# <tex> \Leftarrow </tex>. Построим по раскраске графа набор переменных <tex> \{x_i\}_{i=1}^n </tex>, в котором <tex> x_i </tex> истинно тогда и только тогда, когда <tex> v_i </tex> покрашена в цвет <tex> c_0 </tex>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм.
