1
правка
Изменения
м
категория
Сертификатом для решения данной задачи будет последовательность <tex> \{c_i\}_ {i=1}^{n}</tex>, где <tex> n = |V| </tex>, а <tex> c_i </tex> обозначает цвет <tex>i</tex>-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <tex> [1, k] </tex>. С другой стороны, очевидно, что если задача имеет решение, то такой сертификат существует.
=== Доказательство принадлежности задачи классу NPH ===
[[Файл:3cnfsat.png|thumb|350px|Граф, построенный по формуле <tex refresh dpi=100> (x_1 \lor \lnot x_2 \lor \lnot x_3) \land (\lnot x_1 \lor x_2 \lor \lnot x_3) \land (\lnot x_1 \lor \lnot x_2 \lor x_3)</tex>]]
Сведем задачу [[3CNFSAT]] к данной.<br/>
Пусть дана формула <tex> \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) </tex>, где <tex>a_i</tex>, <tex>b_i</tex> и <tex>c_i</tex> — переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <tex> \{x_i\}_{i=1}^n </tex>.<br/> Заметим следующие тривиальные факты, которые будут использованы при построении графа:
==== Доказательство корректности сведения ====
Покажем теперь, что такой граф будет <tex>(n+1)</tex>-раскрашиваемым тогда и только тогда, когда исходная формула принадлежит <tex> 3CNFSAT </tex>.
# <tex> \Rightarrow </tex>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет <tex>c0c_0</tex>, а вершины, соответствующие ложным термам, — в соответствующие "ложные" цвета.
# <tex> \Leftarrow </tex>. Построим по раскраске графа набор переменных <tex> \{x_i\}_{i=1}^n </tex>, в котором <tex> x_i </tex> истинно тогда и только тогда, когда <tex> v_i </tex> покрашена в цвет <tex> c_0 </tex>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм.
[[Категория:NP]]
[[Категория:Раскраски графов]]
