43
правки
Изменения
м
'''Задача о вершинном покрытии(Языком COVER)''' состоит в нахождении вершинного покрытия размера называется множество пар <tex>\langle G,k \rangle</tex>, где <math>kG</math>- неориентированный граф, где <math>k</math> - некоторое натуральное число.Слово принадлежит языку COVER, если ли граф <math>G</math> содержит вершинное покрытие размера <math>k</math>. Задача о вершинном покрытии является NP-полной.
→Формулировка
==Формулировка==
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
