43
правки
Изменения
м
→Определение
==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.
==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
