43
правки
Изменения
м
→Задача о независимом множестве является NP-трудной
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем по Карпу задачу <math>3-SAT</math> к нашей:
<math>3-SAT \le le_{k} IND</math>
Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.
