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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировки)
(нет различий)

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

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

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

Утверждение

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

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