NP-полнота задачи о раскраске графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
Будем интерпретировать <math> c_i </math> как цвет (соотвественно, вершина <math> c_i </math> всегда покрашена в цвет <math> c_i </math>), причем <math>c_0</math> &mdash; цвет, обозначающий истину.
 
Будем интерпретировать <math> c_i </math> как цвет (соотвественно, вершина <math> c_i </math> всегда покрашена в цвет <math> c_i </math>), причем <math>c_0</math> &mdash; цвет, обозначающий истину.
 
* Для всех <math> i \in \{1 .. n\} </math> добавим в V вершины <math> v_i, \tilde{v_i} </math>, отвечающие <math> x_i </math> и <math> \lnot {x_i} </math> соответственно, и соединим каждую такую пару ребром;
 
* Для всех <math> i \in \{1 .. n\} </math> добавим в V вершины <math> v_i, \tilde{v_i} </math>, отвечающие <math> x_i </math> и <math> \lnot {x_i} </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_j </math>, кроме <math> c_0 </math> и <math> c_i </math>.
Этим мы обеспечили выполнение первого условия из приведенных выше, так как теперь ровно одна вершина из <math> \{v_i, \tilde{v_i}\} </math> окрашена в цвет <math> c_0 </math>, а другая &mdash; в цвет <math> c_i </math>. <br/>
+
Этим мы обеспечили выполнение первого условия из приведённых выше, так как теперь ровно одна вершина из <math> \{v_i, \tilde{v_i}\} </math> окрашена в цвет <math> c_0 </math>, а другая &mdash; в цвет <math> c_i </math>. <br/>
 
Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет <math> c_0 </math>.
 
Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет <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/>
+
* Для этого для каждой скобки вида <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.
+
Покажем теперь, что такой граф будет (n+1)-раскрашиваемым тогда и только тогда, когда исходная формула принадлежит 3CNFSAT.
 
# <math> \Rightarrow </math>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет c0, а вершины, соответствующие ложным термам, &mdash; в соответствующие "ложные" цвета.
 
# <math> \Rightarrow </math>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет c0, а вершины, соответствующие ложным термам, &mdash; в соответствующие "ложные" цвета.
 
# <math> \Leftarrow </math>. Построим по раскраске графа набор переменных <math> \{x_i\}_{i=1}^n </math>, в котором <math> x_i </math> истинно тогда и только тогда, когда <math> v_i </math> покрашена в цвет <math> c_0 </math>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм.
 
# <math> \Leftarrow </math>. Построим по раскраске графа набор переменных <math> \{x_i\}_{i=1}^n </math>, в котором <math> x_i </math> истинно тогда и только тогда, когда <math> v_i </math> покрашена в цвет <math> c_0 </math>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм.

Версия 13:03, 10 марта 2010

Формулировка задачи

Даны граф [math] G = \lt V, E\gt [/math] и число [math] k [/math]. Необходимо проверить, правда ли, что можно раскрасить вершины графа в [math] k [/math] цветов так, чтобы любые две вершины, соединённые ребром, имели разные цвета.

Утверждение

Сформулированная выше задача NP-полна.

Доказательство

Доказательство принадлежности задачи классу NP

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

Доказательство принадлежности задачи классу NPH

Сведем задачу 3CNFSAT к данной.
Пусть дана формула [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] — переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать [math] \{x_i\}_{i=1}^n [/math].
Заметим следующие тривиальные факты, которые будут использованы при построении графа:

  1. Ровно одно выражение из [math] \{x_i, \lnot {x_i}\} [/math] истинно;
  2. [math] \varphi \in 3CNFSAT [/math] тогда и только тогда, когда существует набор, обращающий каждую скобку в истину.

Построим множества V и E будущего графа следующим образом:

  • [math] V = \{c_i\}_{i=0}^n [/math];
  • [math] E = \{\lt c_i, c_j\gt \}_{i,j=0, i \ne j}^n [/math].

Будем интерпретировать [math] c_i [/math] как цвет (соотвественно, вершина [math] c_i [/math] всегда покрашена в цвет [math] c_i [/math]), причем [math]c_0[/math] — цвет, обозначающий истину.

  • Для всех [math] i \in \{1 .. n\} [/math] добавим в V вершины [math] v_i, \tilde{v_i} [/math], отвечающие [math] x_i [/math] и [math] \lnot {x_i} [/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].
Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет [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], мы условились называть «ложными»).

Доказательство корректности сведения

Покажем теперь, что такой граф будет (n+1)-раскрашиваемым тогда и только тогда, когда исходная формула принадлежит 3CNFSAT.

  1. [math] \Rightarrow [/math]. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет c0, а вершины, соответствующие ложным термам, — в соответствующие "ложные" цвета.
  2. [math] \Leftarrow [/math]. Построим по раскраске графа набор переменных [math] \{x_i\}_{i=1}^n [/math], в котором [math] x_i [/math] истинно тогда и только тогда, когда [math] v_i [/math] покрашена в цвет [math] c_0 [/math]. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм.