Изменения
Нет описания правки
[[Файл:Cover.jpg|thumb|right|150x150px|Пример минимального вершинного покрытия графа]]
{{Определение|neat=neat|definition=
'''Вершинным покрытием''' (англ. '''Vertex covering''', '''VC''') графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что у каждого ребра любое ребро этого графа инцидентно хотя бы один одной вершине из концов входит в множества <tex>S</tex>.
}}
{{Определение|neat=neat|definition=
'''Минимальным вершинным покрытием''' (англ. '''Minimum vertex covering''', '''MVC''') графа <tex>G=(V,E)</tex> называется вершинное покрытие минимальной мощности, состоящее из наименьшего числа вершин.
}}
