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