Изменения

Множество [[Основные определения теории графов#def_graph_edge_1|ребер]] (вершин) называется '''независимым''' (англ. ''independent''), если никакие его два элемента не смежны.

}}

|id=def_3

'''Вершинным покрытием''' (англ. ''vertex cover'') графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.

}}