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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
=== Доказательство принадлежности задачи классу NPH ===
 
=== Доказательство принадлежности задачи классу NPH ===
 
Сведем задачу 3CNFSAT к данной.<br/>
 
Сведем задачу 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> - переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <math> \{x_i\}_{i=1}^n </math>.
+
Пусть дана <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>.<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>
 +
Построим множества V и E будущего графа следущим образом:
 +
* <math> V = \{c_j\}_{j=0}^m </math>;
 +
* <math> E = \{<c_i, c_j>\}_{i,j=0, i \ne j}^m </math>;
 +
Будем интерпретировать <math> c_i </math> как цвет, причем <math>c_0</math> - цвет, обозначающий истину.
 +
* <math> \forall i \in \{1 .. n\} </math> добавим в V вершины <math> v_i, \tilde{v_i}\}_{i=1}^n </math>, отвечающие <math> x_i </math> и <math> \lnot {x_i} </math> соответственно;

Версия 23:35, 9 марта 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].
Заметим следующие тривиальные факты, которые будут использованы при построении графа:

  • Ровно одно выражение из [math] \{x_i, \lnot {x_i}\} [/math] истинно;
  • [math] \varphi \in 3CNFSAT \Leftrightarrow \forall {j} (a_j \lor b_j \lor c_j) = 1 [/math]

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

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

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

  • [math] \forall i \in \{1 .. n\} [/math] добавим в V вершины [math] v_i, \tilde{v_i}\}_{i=1}^n [/math], отвечающие [math] x_i [/math] и [math] \lnot {x_i} [/math] соответственно;