Редактирование: NP-полнота задачи о раскраске графа

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Формулировка задачи==
 
== Формулировка задачи==
Даны граф <tex> G = \langle V, E \rangle </tex> и число <tex> k </tex>. Необходимо проверить, правда ли, что можно раскрасить вершины графа в <tex> k </tex> цветов так, чтобы любые две вершины, соединённые ребром, имели разные цвета.
+
Даны граф <math> G = <V, E> </math> и число <math> k </math>. Необходимо проверить, правда ли, что можно раскрасить вершины графа в <math> k </math> цветов так, чтобы любые две вершины, соединённые ребром, имели разные цвета.
  
 
== Утверждение ==
 
== Утверждение ==
Сформулированная выше задача [[NP-полнота|NP-полна]].
+
Сформулированная выше задача NP-полна.
  
 
== Доказательство ==
 
== Доказательство ==
 
=== Доказательство принадлежности задачи классу NP ===
 
=== Доказательство принадлежности задачи классу NP ===
Сертификатом для решения данной задачи будет последовательность <tex> \{c_i\}_ {i=1}^{n}</tex>, где <tex> n = |V| </tex>, а <tex> c_i </tex> обозначает цвет <tex>i</tex>-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <tex> [1, k] </tex>. С другой стороны, очевидно, что если задача имеет решение, то такой сертификат существует.
+
Сертификатом для решения данной задачи будет последовательность <math> \{c_i\}_ {i=1}^{n}</math>, где <math> n = |V| </math>, а <math> c_i </math> обозначает цвет i-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <math> [1, k] </math>.
 
=== Доказательство принадлежности задачи классу NPH ===
 
=== Доказательство принадлежности задачи классу 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/>
Сведем задачу [[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> &mdash; переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <math> \{x_i\}_{i=1}^n </math>.<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> &mdash; переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <tex> \{x_i\}_{i=1}^n </tex>.<br/> Заметим следующие тривиальные факты, которые будут использованы при построении графа:
+
# Ровно одно выражение из <math> \{x_i, \lnot {x_i}\} </math> истинно;
# Ровно одно выражение из <tex> \{x_i, \lnot {x_i}\} </tex> истинно;
+
# <math> \varphi \in 3CNFSAT \Leftrightarrow \forall {j} (a_j \lor b_j \lor c_j) = 1 </math>
# <tex> \varphi \in 3CNFSAT </tex> тогда и только тогда, когда существует набор, обращающий каждую скобку в истину.
+
Построим множества V и E будущего графа следущим образом:
Построим множества V и E будущего графа следующим образом:
+
* <math> V = \{c_i\}_{i=0}^n </math>;
* <tex> V = \{c_i\}_{i=0}^n </tex>;
+
* <math> E = \{<c_i, c_j>\}_{i,j=0, i \ne j}^n </math>;
* <tex> E = \{\langle c_i, c_j \rangle \}_{i,j=0, i \ne j}^n </tex>.
+
Будем интерпретировать <math> c_i </math> как цвет (соотвественно, вершина <math> c_i </math> всегда покрашена в цвет <math> c_i </math>), причем <math>c_0</math> &mdash; цвет, обозначающий истину.
Будем интерпретировать <tex> c_i </tex> как цвет (соотвественно, вершина <tex> c_i </tex> всегда покрашена в цвет <tex> c_i </tex>), причем <tex>c_0</tex> &mdash; цвет, обозначающий истину, а все остальные цвета означают ложь).
+
* <math> \forall i \in \{1 .. n\} </math> добавим в V вершины <math> v_i, \tilde{v_i} </math>, отвечающие <math> x_i </math> и <math> \lnot {x_i} </math> соответственно, и соединим каждую такую пару ребром;
* Для всех <tex> i \in \{1 .. n\} </tex> добавим в V вершины <tex> v_i, \tilde{v_i} </tex>, отвечающие <tex> x_i </tex> и <tex> \lnot {x_i} </tex> соответственно, и соединим каждую такую пару ребром;
+
* <math> \forall i \in \{1 .. n\} </math> соединим каждую вершину из <math> \{v_i, \tilde{v_i}\} </math> со всеми <math> c_j </math>, кроме <math> c_0 </math> и <math> c_i </math>.
* Каждую вершину из <tex> \{v_i, \tilde{v_i}\} </tex> соединим рёбрами со всеми <tex> c_j </tex>, кроме <tex> c_0 </tex> и <tex> c_i </tex>.
+
Этим мы обеспечили выполнение первого условия из приведенных выше, так как теперь ровно одна вершина из <math> \{v_i, \tilde{v_i}\} </math> окрашена в цвет <math> c_0 </math>, а другая &mdash; в цвет <math> c_i </math> <br/>
Этим мы обеспечили выполнение первого условия из приведённых выше, так как теперь ровно одна вершина из <tex> \{v_i, \tilde{v_i}\} </tex> окрашена в цвет <tex> c_0 </tex>, а другая &mdash; в цвет <tex> c_i </tex>. <br/>
+
Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет <math> c_0 </math>.
Осталось сделать так, чтобы возможность сделать истинной каждую скобку соответствовала необходимости покрасить хотя бы одну из вершин, соответствующих переменным в ней, в цвет <tex> c_0 </tex>.
+
* Для этого для каждой скобки вида <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/>
* Для этого для каждой скобки вида <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>-раскрашиваемым тогда и только тогда, когда исходная формула принадлежит <tex> 3CNFSAT </tex>.
+
Покажем теперь, что такой граф будет (n+1)-раскрашиваемым тогда и только тогда, когда исходная формула принадлежала 3CNFSAT.
# <tex> \Rightarrow </tex>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет <tex>c_0</tex>, а вершины, соответствующие ложным термам, &mdash; в соответствующие "ложные" цвета.
+
# <math> \Rightarrow </math>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет c0, а вершины, соответствующие ложным термам, &mdash; в соответствующие "ложные" цвета.
# <tex> \Leftarrow </tex>. Построим по раскраске графа набор переменных <tex> \{x_i\}_{i=1}^n </tex>, в котором <tex> x_i </tex> истинно тогда и только тогда, когда <tex> v_i </tex> покрашена в цвет <tex> c_0 </tex>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм.
+
# <math> \Leftarrow </math>. Построим по раскраске графа набор переменных <math> \{x_i\}_{i=1}^n </math>, в котором <math> x_i </math> истинно тогда и только тогда, когда <math> v_i </math> покрашена в цвет <math> c_0 </math>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истину, так как по постронию в каждой скобке есть хотя бы один истинный терм.
 
 
[[Категория:NP]]
 
[[Категория:Раскраски графов]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)