Изменения

Пусть задан неориентированный граф Языком IND называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> и натуральное число - неориентированный граф, <math>k</math>- натуральное число. '''Задача о независимом множестве(Слово принадлежит языку IND)''' решает вопрос о том, содержит ли если граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.Задача о независимом множестве является [[Понятие 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{neg x}</math>.

<math>(\overline{neg x}\lor y\lor z)\land (x \lor y \lor \overline{neg z}) \to</math>[[Файл:IND_GRAPH.png]]

Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменнаяодин литерал, принимающая принимающий значение “правда” (учитываем отрицание, если оно есть)“истина”. Выберем соответствующую переменную в качестве вершины ему вершину в графе. Выбранное Полученное множество вершин является независимым, так как ребрами рёбрами соединены только те вершины, которые соответствуют переменным литералам из одной скобки(а мы выбирали только одну переменную один литерал из каждой скобки) и пары вершин, которым соответствуют пары переменных а так же вершины вида <math>x,\overline{neg x}</math>, которые соответствующие литералы которых не могут одновременно принимать значение “правда”“истина”. Пусть теперь в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”соответствующего литерала “истина”. Это можно сделать, так как нет рёбер между вершинами вида <math>x,\neg x</math>. Тогда в каждой скобке, будет хотя бы одна переменнаяодин литерал, имеющая имеющий значение “правда”“истина”, значит вся формула будет принимать значение “правда”“истина”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.