Изменения

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

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

67 байт убрано, 22:09, 9 марта 2010
Нет описания правки
== Доказательство ==
# '''Сперва покажем принадлежность === Доказательство принадлежности задачи классу NP.'''===
Сертификатом для решения данной задачи будет последовательность <math> \{c_i\}_ {i=1}^{n}</math>, где <math> n = |V| </math>, а <math> c_i </math> обозначает цвет i-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <math> [1, k] </math>.
# '''Для завершения доказательства необходимо доказать принадлежность === Доказательство принадлежности задачи классу NPH.'''===
45
правок

Навигация