1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Формулировка==
Языком CLIQUE называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку CLIQUE, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром. Задача о клике является [[Понятие NP-трудной и NP-полной задачи|NP-полной]].
==Доказательство NP-полноты==
===Задача о клике принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой.
[[Категория:NP]]
