27
правок
Изменения
Нет описания правки
<tex> \forall u, v \in S</tex> <tex>uv \notin E</tex>.
}}
}}
[[Файл:Independent_set_graph.gif|thumb|left|300px|Множество вершин синего цвета — максимальное независимое множество.]]
<br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><brclear="all"/>
==Связь вершинного покрытия и независимого множества==
|proof=
Пусть <tex>M</tex> произвольное максимальное независимое множество вершин графа <tex>G=(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>|S| \le leqslant |V \backslash M|</tex> или <tex>|S| + |M| \le leqslant |V|</tex>.
Рассмотрим произвольное минимальное вершинное покрытие графа <tex>S</tex>. Так как каждое ребро инцидентно хотя бы одной вершине из <tex>S</tex>, то <tex>V \backslash S</tex> является независимым множеством. Тогда <tex>|V \backslash S| \le leqslant |M|</tex> или <tex>|V| \le leqslant |S| + |M|</tex>.
Значит, <tex>|V| = |M| + |S|</tex>, и <tex>V \backslash S</tex> является максимальным независимым множеством, а <tex>V \backslash M</tex> — минимальным вершинным покрытием.
==См. также ==
*[[Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольных_графах|Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]].
==Источникиинформации==1. * [http://en.wikipedia.org/wiki/Vertex_cover_problem Вершинное покрытиеWikipedia {{---}} Vertex cover].<br/>2. * [http://en.wikipedia.org/wiki/Independent_set_(graph_theory) Независимое множествоWikipedia {{---}} Independent set].<br/>
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]
