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