Изменения

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

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

10 байт добавлено, 12:09, 10 марта 2010
Нет описания правки
== Формулировка задачи==
Даны граф <math> G = <V, E> </math> и число <math> k </math>. Нужно Необходимо проверить, правда ли, что можно раскрасить вершины графа в <math> k </math> цветов так, чтобы любые две вершины, соединённые ребром, имели разные цвета.
== Утверждение ==
45
правок

Навигация