Изменения

===Независимое множество===[[Файл:Independent_set_graph.gif|thumb|right|150x150px|Пример независимого множества вершин графа.]]{{Определение|neat=neat|definition='''Независимым множеством вершин''''' (англ. '''Independent independent vertex set)''') графа <tex>G=(V,E)</tex> называется такое множество подмножество <tex>S</tex> множества вершин графа <tex>IVSV</tex> , что<tex> \forall u, v \in IVSS</tex> <tex>uv \notin E</tex>.

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

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

Рассмотрим Пусть <tex>M</tex> произвольное максимальное независимое множество вершин графа <tex>MIVSG=(V,E)</tex> графа, а <tex>S</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>|MVCS| \le leqslant |V \backslash MIVSM|</tex> или <tex>|MVCS| + |MIVSM| \le leqslant |V|</tex>.

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

Значит, <tex>|V| = |MIVSM| + |MVCS|</tex>, и <tex>V \backslash MVCS</tex> является максимальным независимым множеством, а <tex>V \backslash MIVSM</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/>