Изменения

==Формулировка==

Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.

==Доказательство NP-полноты==

Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.