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

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

Определение:

Независимым множеством вершин (англ. 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]

См. также

• Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах.

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

• Wikipedia — Vertex cover
• Wikipedia — Independent set