43
правки
Изменения
создание странички
==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем задачу <math>3-SAT</math> к нашей:
<math>3-SAT \le IND</math>
Пусть задана булева формула в <math>3-SAT</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>[[Файл:Example.jpg]]
Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда”. Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.
===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о независимом множестве(IND)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, никакая пара вершин в котором не соединена ребром.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о независимом множестве является NP-трудной===
Для доказательства этого сведем задачу <math>3-SAT</math> к нашей:
<math>3-SAT \le IND</math>
Пусть задана булева формула в <math>3-SAT</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>[[Файл:Example.jpg]]
Докажем, что формула выполнима тогда и только тогда, когда в соответствующем графе есть независимое множество из <math>k</math> вершин. Пусть формула выполнима, тогда в каждой скобке есть хотя бы одна переменная, принимающая значение “правда”. Выберем соответствующую переменную в качестве вершины в графе. Выбранное множество вершин является независимым, так как ребрами соединены только вершины, которые соответствуют переменным из одной скобки(а мы выбирали только одну переменную из каждой скобки) и пары вершин, которым советуют пары переменных вида <math>x,\overline{x}</math>, которые не могут одновременно принимать значение “правда”. Пусть в графе есть независимое множество, размера <math>k</math>. Тогда в каждой тройке вершин, соответствующих некоторой скобке, выбрана ровно одна вершина. Установим значение соответствующей переменной “правда”. Тогда в каждой скобке, будет хотя бы одна переменная, имеющая значение “правда”, значит вся формула будет принимать значение “правда”. Построение по формуле соответствующего графа можно сделать за полиномиальное время.
===Задача о независимом множестве принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин независимым.
