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

Материал из Викиконспекты
Перейти к: навигация, поиск

Определения

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

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


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








Пример

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

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

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

Рассмотрим произвольное максимальное независимое множество вершин графа [math]M[/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]|MVC| \le |V \backslash M|[/math] или [math]|MVC| + |M| \le |V|[/math].

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

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

См. также

Источники