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

Материал из Викиконспекты
Версия от 18:21, 22 декабря 2010; 192.168.0.2 (обсуждение) (Новая страница: «==Определения== ===Независимое множество=== {{Определение|definition= Независимым множеством верш…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определения

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

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


Определение:
Максимальным независимым множеством [math]MIVS[/math] [math](Maximum[/math] [math]independent[/math] [math]vertex[/math] [math]set)[/math],называется независимое множество максимальной мощности


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

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

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

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

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

Источники

1.Vertex cover.
2.Independent set.
3.Мирзаянов М.Р. Паросочетания и смежные задачи.