43
правки
Изменения
м
Задача Для доказательства NP-полноты задачи о нахождении клики размера <math>k</math> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из тогоклике покажем, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда она является NP-трудной и только тогда, когда в дополнении графа найдется множество размера <math>k</math> попарно не соединенных ребрами вершинпринадлежит классу NP.
→Доказательство NP-полноты
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
==Доказательство NP-полноты==
