Связь вершинного покрытия и независимого множества — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 4 участников)
Строка 1: Строка 1:
==Определения==
 
  
===Независимое множество===
+
 
[[Файл:Independent_set_graph.gif|thumb|right|150x150px|Пример независимого множества вершин графа.]]
+
==Независимое множество==
{{Определение|neat=neat|definition=
+
{{Определение|definition=
'''Независимым множеством вершин''' (англ. '''Independent vertex set''') графа <tex>G</tex> называется такое подмножество <tex>S</tex> множества вершин графа V, что
+
'''Независимым множеством вершин''' ''(англ. independent vertex set)'' графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что
 
<tex> \forall u, v \in S</tex> <tex>uv \notin E</tex>.
 
<tex> \forall u, v \in S</tex> <tex>uv \notin E</tex>.
 
}}
 
}}
{{Определение|neat = neat|definition=
+
{{Определение|definition=
'''Максимальным независимым множеством''' (англ. '''Maximum independent vertex set''') называется независимое множество вершин максимальной мощности.
+
'''Максимальным независимым множеством''' ''(англ. maximum independent set)'' называется независимое множество вершин максимальной мощности.
 
}}
 
}}
<br/>
+
 
<br/>
+
[[Файл:Independent_set_graph.gif|thumb|left|300px|Множество вершин синего цвета — максимальное независимое множество.]]
<br/>
+
<br clear="all"/>
<br/>
 
<br/>
 
<br/>
 
<br/>
 
<br/>
 
  
 
==Связь вершинного покрытия и независимого множества==
 
==Связь вершинного покрытия и независимого множества==
Строка 23: Строка 17:
 
Дополнение минимального вершинного покрытия является максимальным независимым множеством.
 
Дополнение минимального вершинного покрытия является максимальным независимым множеством.
 
|proof=
 
|proof=
Рассмотрим произвольное максимальное независимое множество вершин графа <tex>M</tex>. Из определения следует, что любое ребро соединяет либо вершину из <tex>M</tex> и <tex>V \backslash M</tex>, либо вершины множества <tex>V \backslash M</tex>. Таким образом, каждое
+
Пусть <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>|MVC| \le |V \backslash M|</tex> или <tex>|MVC| + |M| \le |V|</tex>.
+
ребро инцидентно некоторой вершине множества <tex>V \backslash M</tex>, то есть <tex>V \backslash M</tex> является некоторым вершинным покрытием. Тогда <tex>|S| \leqslant |V \backslash M|</tex> или <tex>|S| + |M| \leqslant |V|</tex>.
  
Рассмотрим произвольное минимальное вершинное покрытие графа <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>S</tex>. Так как каждое ребро инцидентно хотя бы одной вершине из <tex>S</tex>, то <tex>V \backslash S</tex> является независимым множеством. Тогда <tex>|V \backslash S| \leqslant |M|</tex> или <tex>|V| \leqslant |S| + |M|</tex>.
  
Значит, <tex>|V| = |M| + |MVC|</tex>, и <tex>V \backslash MVC</tex> является максимальным независимым множеством, а <tex>V \backslash М</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 Вершинное покрытие].<br/>
+
* [http://en.wikipedia.org/wiki/Vertex_cover_problem Wikipedia {{---}} Vertex cover]
2. [http://en.wikipedia.org/wiki/Independent_set_(graph_theory) Независимое множество].<br/>
+
* [http://en.wikipedia.org/wiki/Independent_set_(graph_theory) Wikipedia {{---}} Independent set]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о паросочетании]]
 
[[Категория: Задача о паросочетании]]

Текущая версия на 19:07, 4 сентября 2022


Независимое множество

Определение:
Независимым множеством вершин (англ. independent vertex set) графа [math]G=(V,E)[/math] называется такое подмножество [math]S[/math] множества вершин графа [math]V[/math], что [math] \forall u, v \in S[/math] [math]uv \notin E[/math].


Определение:
Максимальным независимым множеством (англ. maximum independent set) называется независимое множество вершин максимальной мощности.


Множество вершин синего цвета — максимальное независимое множество.


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

Теорема:
Дополнение минимального вершинного покрытия является максимальным независимым множеством.
Доказательство:
[math]\triangleright[/math]

Пусть [math]M[/math] произвольное максимальное независимое множество вершин графа [math]G=(V,E)[/math], а [math]S[/math] его минимальное вершинное покрытие. Из определения следует, что любое ребро соединяет либо вершину из [math]M[/math] и [math]V \backslash M[/math], либо вершины множества [math]V \backslash M[/math]. Таким образом, каждое ребро инцидентно некоторой вершине множества [math]V \backslash M[/math], то есть [math]V \backslash M[/math] является некоторым вершинным покрытием. Тогда [math]|S| \leqslant |V \backslash M|[/math] или [math]|S| + |M| \leqslant |V|[/math].

Рассмотрим произвольное минимальное вершинное покрытие графа [math]S[/math]. Так как каждое ребро инцидентно хотя бы одной вершине из [math]S[/math], то [math]V \backslash S[/math] является независимым множеством. Тогда [math]|V \backslash S| \leqslant |M|[/math] или [math]|V| \leqslant |S| + |M|[/math].

Значит, [math]|V| = |M| + |S|[/math], и [math]V \backslash S[/math] является максимальным независимым множеством, а [math]V \backslash M[/math] — минимальным вершинным покрытием.
[math]\triangleleft[/math]

См. также

Источники информации