Изменения
Нет описания правки
[[Файл:Independent_set_graph.gif|300px]]
<br/>
Множество вершин синего цвета - — минимальное независимое множество.
==Связь вершинного покрытия и независимого множества==
Рассмотрим произвольное минимальное вершинное покрытие графа <tex>MVC</tex>. Так как каждое ребро инцидентно хотя бы одной вершине из <tex>MVC</tex>, то <tex>V \backslash MVC</tex> является независимым множеством. Тогда <tex>|V \backslash MVC| \le |M|</tex> или <tex>|V| \le |MVC| + |M|</tex>.
Значит, <tex>|V| = |M| + |MVC|</tex>, и <tex>V \backslash MVC</tex> является максимальным независимым множеством, а <tex>V \backslash M</tex> - — минимальным вершинным покрытием.
}}
