43
правки
Изменения
м
→Задача о вершинном покрытии является NP-трудной
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства [[Сведение по Карпу||сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.
<math>IND \le_{k} COVER</math>
