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