Изменения

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