Связь вершинного покрытия и независимого множества — различия между версиями
(→Связь вершинного покрытия и независимого множества) |
(→Связь вершинного покрытия и независимого множества) |
||
Строка 12: | Строка 12: | ||
<br/><br/> | <br/><br/> | ||
+ | <br/> | ||
+ | <br/> | ||
<br/> | <br/> | ||
==Связь вершинного покрытия и независимого множества== | ==Связь вершинного покрытия и независимого множества== |
Версия 23:34, 15 января 2011
Содержание
Определения
Независимое множество
Определение:
Независимым множеством вершин графа
называется такое множество , что
.
Определение:
Максимальным независимым множеством
называется IVS максимальной мощности.
Связь вершинного покрытия и независимого множества
Теорема: |
Дополнение минимального вершинного покрытия является максимальным независимым множеством. |
Доказательство: |
Рассмотрим произвольное графа. Из определения следует, что любое ребро соединяет либо вершину из и , либо вершины множества . Таким образом, каждое ребро инцидентно некоторой вершине множества , то есть является некоторым вершинным покрытием. Тогда или .Рассмотрим произвольное Значит, графа. Так как каждое ребро инцидентно хотя бы одной вершине из , то является независимым множеством. Тогда или . , и является максимальным независимым множеством, а - минимальным вершинным покрытием. |
См. также
Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах.