Изменения

Перейти к: навигация, поиск

NP-полнота задачи о вершинном покрытии

27 байт добавлено, 01:01, 11 октября 2019
Нет описания правки
===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> рёбер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.
 
[[Категория:NP]]
202
правки

Навигация