Изменения

'''Независимым множеством вершин''' (англ. '''Independent vertex set''') графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа V, что

'''Максимальным независимым множеством''' (англ. '''Maximum independent vertex set''') называется независимое множество вершин максимальной мощности.

[[Файл:Independent_set_graph.gif|thumb|left|300px]]<br/>|Множество вершин синего цвета — максимальное независимое множество.]]<br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/>

Рассмотрим Пусть <tex>M</tex> произвольное максимальное независимое множество вершин графа <tex>MG=(V,E)</tex>, а <tex>S</tex>его минимальное вершинное покрытие. Из определения следует, что любое ребро соединяет либо вершину из <tex>M</tex> и <tex>V \backslash M</tex>, либо вершины множества <tex>V \backslash M</tex>. Таким образом, каждоеребро инцидентно некоторой вершине множества <tex>V \backslash M</tex>, то есть <tex>V \backslash M</tex> является некоторым вершинным покрытием. Тогда мощность минимального вершинного покрытия <tex>|MVCS| \le |V \backslash M|</tex> или <tex>|MVCS| + |M| \le |V|</tex>.

Рассмотрим произвольное минимальное вершинное покрытие графа <tex>MVCS</tex>. Так как каждое ребро инцидентно хотя бы одной вершине из <tex>MVCS</tex>, то <tex>V \backslash MVCS</tex> является независимым множеством. Тогда <tex>|V \backslash MVCS| \le |M|</tex> или <tex>|V| \le |MVCS| + |M|</tex>.

Значит, <tex>|V| = |M| + |MVCS|</tex>, и <tex>V \backslash MVCS</tex> является максимальным независимым множеством, а <tex>V \backslash M</tex> — минимальным вершинным покрытием.