Изменения

'''Независимым множеством вершин''' (англ. '''Independent vertex set''') графа <tex>G</tex> называется такое множество подмножество <tex>IVSS</tex> множества вершин графа V, что<tex> \forall u, v \in IVSS</tex> <tex>uv \notin E</tex>.

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

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

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

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