200
правок
Изменения
м
Нет описания правки
Множество [[Основные определения теории графов#def_graph_edge_1|ребер]] (вершин) называется '''независимым''' (англ. ''independent''), если никакие его два элемента не смежны.
}}
{{Определение|
|id=def_3
|definition=
'''Вершинным покрытием''' (англ. ''vertex cover'') графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.
}}
