Просмотр исходного текста страницы Связь вершинного покрытия и независимого множества

==Определения==

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

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

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

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

==См. также ==
[[Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольных_графах|Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]].

==Источники==
1. [http://en.wikipedia.org/wiki/Vertex_cover_problem Вершинное покрытие].<br/>
2. [http://en.wikipedia.org/wiki/Independent_set_(graph_theory) Независимое множество].<br/>

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]