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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Независимое множество)
(Определения)
Строка 4: Строка 4:
 
[[Файл:Independent_set_graph.gif|thumb|right|150x150px|Пример независимого множества вершин графа.]]
 
[[Файл:Independent_set_graph.gif|thumb|right|150x150px|Пример независимого множества вершин графа.]]
 
{{Определение|neat=neat|definition=
 
{{Определение|neat=neat|definition=
Независимым множеством вершин графа <tex>G</tex> называется такое множество <tex>IVS</tex> <tex>(Independent</tex> <tex>vertex</tex> <tex>set) </tex>, что
+
'''Независимым множеством вершин''' (англ. '''Independent vertex set''') графа <tex>G</tex> называется такое множество <tex>IVS</tex> , что
 
<tex> \forall u, v \in IVS</tex> <tex>uv \notin E</tex>.
 
<tex> \forall u, v \in IVS</tex> <tex>uv \notin E</tex>.
 
}}
 
}}
 
{{Определение|neat = neat|definition=
 
{{Определение|neat = neat|definition=
Максимальным независимым множеством <tex>MIVS</tex> <tex>(Maximum</tex> <tex>independent</tex> <tex>vertex</tex> <tex>set)</tex> называется IVS максимальной мощности.
+
'''Максимальным независимым множеством''' (англ. '''Maximum independent vertex set''', '''MIVS''') называется IVS максимальной мощности.
 
}}
 
}}
 
<br/>
 
<br/>

Версия 05:16, 22 января 2011

Определения

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

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


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









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

Теорема:
Дополнение минимального вершинного покрытия является максимальным независимым множеством.
Доказательство:
[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. Вершинное покрытие.
2. Независимое множество.