43
правки
Изменения
м
→Задача о независимом множестве является NP-трудной
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого [[Сведение по Карпу|сведем по Карпу ]] задачу <math>3-SAT3SAT</math> к нашей:
<math>3-SAT 3SAT \le_{k} IND</math>
Пусть задана булева формула в <math>3-SAT3SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.
<math>(\overline{x}\lor y\lor z)\land (x \lor y \lor \overline{z}) \to</math>[[Файл:IND_GRAPH.png]]
