Изменения

Даны граф <tex> G = \langle V, E \rangle </tex> и число <mathtex> k </mathtex>. Необходимо проверить, правда ли, что можно раскрасить вершины графа в <mathtex> k </mathtex> цветов так, чтобы любые две вершины, соединённые ребром, имели разные цвета.

Сертификатом для решения данной задачи будет последовательность <mathtex> \{c_i\}_ {i=1}^{n}</mathtex>, где <mathtex> n = |V| </mathtex>, а <mathtex> c_i </mathtex> обозначает цвет <tex>i</tex>-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <mathtex> [1, k] </mathtex>. С другой стороны, очевидно, что если задача имеет решение, то такой сертификат существует.

Пусть дана формула <mathtex> \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) </mathtex>, где <mathtex>a_i</mathtex>, <mathtex>b_i</mathtex> и <mathtex>c_i</mathtex> &mdash; переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <mathtex> \{x_i\}_{i=1}^n </mathtex>.<br/> Заметим следующие тривиальные факты, которые будут использованы при построении графа:# Ровно одно выражение из <mathtex> \{x_i, \lnot {x_i}\} </mathtex> истинно;# <mathtex> \varphi \in 3CNFSAT </mathtex> тогда и только тогда, когда существует набор, обращающий каждую скобку в истину.

* <mathtex> V = \{c_i\}_{i=0}^n </mathtex>;* <mathtex> E = \{<\langle c_i, c_j>\rangle \}_{i,j=0, i \ne j}^n </mathtex>.Будем интерпретировать <mathtex> c_i </mathtex> как цвет (соотвественно, вершина <mathtex> c_i </mathtex> всегда покрашена в цвет <mathtex> c_i </mathtex>), причем <mathtex>c_0</mathtex> &mdash; цвет, обозначающий истину, а все остальные цвета означают ложь).* Для всех <mathtex> i \in \{1 .. n\} </mathtex> добавим в V вершины <mathtex> v_i, \tilde{v_i} </mathtex>, отвечающие <mathtex> x_i </mathtex> и <mathtex> \lnot {x_i} </mathtex> соответственно, и соединим каждую такую пару ребром;* Каждую вершину из <mathtex> \{v_i, \tilde{v_i}\} </mathtex> соединим рёбрами со всеми <mathtex> c_j </mathtex>, кроме <mathtex> c_0 </mathtex> и <mathtex> c_i </mathtex>.Этим мы обеспечили выполнение первого условия из приведённых выше, так как теперь ровно одна вершина из <mathtex> \{v_i, \tilde{v_i}\} </mathtex> окрашена в цвет <mathtex> c_0 </mathtex>, а другая &mdash; в цвет <mathtex> c_i </mathtex>. <br/>Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет <mathtex> c_0 </mathtex>.* Для этого для каждой скобки вида <mathtex> ([\lnot]x_i \lor [\lnot] x_j \lor [\lnot] x_k)_l </mathtex> добавим вершину <mathtex> d_l </mathtex>, соединив её с соответствующими <mathtex> v_i (\tilde{v_i}), v_j(\tilde{v_j}), v_k(\tilde{v_k}) </mathtex>, а также со всеми <mathtex> c_i </mathtex>, кроме <mathtex> c_i, c_j, c_k </mathtex>. Тем самым, <mathtex> d_l </mathtex> «не даёт» покрасить все три вершины, отвечающие термам в скобке, в «ложный» цвет (напомним, что все цвета, кроме <mathtex> c_0 </mathtex>, мы условились называть «ложными»).<br/>

Покажем теперь, что такой граф будет <tex>(n+1)</tex>-раскрашиваемым тогда и только тогда, когда исходная формула принадлежит <tex> 3CNFSAT</tex>.# <mathtex> \Rightarrow </mathtex>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет c0<tex>c_0</tex>, а вершины, соответствующие ложным термам, &mdash; в соответствующие "ложные" цвета.# <mathtex> \Leftarrow </mathtex>. Построим по раскраске графа набор переменных <mathtex> \{x_i\}_{i=1}^n </mathtex>, в котором <mathtex> x_i </mathtex> истинно тогда и только тогда, когда <mathtex> v_i </mathtex> покрашена в цвет <mathtex> c_0 </mathtex>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм. [[Категория:NP]]