Изменения
Новая страница: «==Определения== ===Независимое множество=== {{Определение|definition= Независимым множеством верш…»
==Определения==
===Независимое множество===
{{Определение|definition=
Независимым множеством вершин графа <tex>G</tex> называется такое множество <tex>IVS</tex> <tex>(Independent</tex> <tex>vertex</tex> <tex>set) </tex>, что
<tex> \forall u, v \in IVS</tex> <tex>uv \notin E</tex>.
}}
{{Определение|definition=
Максимальным независимым множеством <tex>MIVS</tex> <tex>(Maximum</tex> <tex>independent</tex> <tex>vertex</tex> <tex>set)</tex>,называется независимое множество максимальной мощности
}}
==Связь вершинного покрытия и независимого множества==
{{Теорема|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 Vertex cover].<br/>
2.[http://en.wikipedia.org/wiki/Independent_set_(graph_theory) Independent set].<br/>
3.Мирзаянов М.Р. Паросочетания и смежные задачи.
===Независимое множество===
{{Определение|definition=
Независимым множеством вершин графа <tex>G</tex> называется такое множество <tex>IVS</tex> <tex>(Independent</tex> <tex>vertex</tex> <tex>set) </tex>, что
<tex> \forall u, v \in IVS</tex> <tex>uv \notin E</tex>.
}}
{{Определение|definition=
Максимальным независимым множеством <tex>MIVS</tex> <tex>(Maximum</tex> <tex>independent</tex> <tex>vertex</tex> <tex>set)</tex>,называется независимое множество максимальной мощности
}}
==Связь вершинного покрытия и независимого множества==
{{Теорема|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 Vertex cover].<br/>
2.[http://en.wikipedia.org/wiki/Independent_set_(graph_theory) Independent set].<br/>
3.Мирзаянов М.Р. Паросочетания и смежные задачи.
