Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач. Вершинное покрытие для неориентированного графа G = (V,E) — это множество его вершин S, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из S...