43
правки
Изменения
м
→Задача о вершинном покрытии является NP-трудной
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве ]] к нашей.
<math>IND \le_{k} COVER</math>
Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время
===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.
