43
правки
Изменения
м
→Доказательство NP-полноты
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.
