Задача о вершинном покрытии: различия между версиями

'''Вершинное покрытие''' для неориентированного [[Граф (математика)|графа]] <math>G = (V, E)</math> это [[множество]] его вершин <math>S</math>, такое что, у каждого ребра хотя бы один из концов входит в ''S''.

 

 

'''Размером''' (size) вершинного покрытия называется число входящих в него вершин.