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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировки)
 
Строка 6: Строка 6:
  
 
== Доказательство ==
 
== Доказательство ==
 +
# '''Сперва покажем принадлежность задачи классу NP.'''<br/>
 +
Сертификатом для решения данной задачи будет последовательность <math> \{c_i\}_ {i=1}^{n}</math>, где <math> n = |V| </math>, а <math> c_i </math> обозначает цвет i-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <math> [1, k] </math>.

Версия 21:52, 9 марта 2010

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

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

Утверждение

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

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

  1. Сперва покажем принадлежность задачи классу NP.

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