Изменения
Нет описания правки
==Определения==
===Минимальное вершинное покрытие===
{{Определение|neat=neat|definition=
'''Минимальным вершинным покрытием''' (англ. '''Minimum vertex covering''', '''MVC''') графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин.
}}
<br/>
<br/>
<br/>
<br/>
<br/>
==Пример==
[[Файл:Cover.jpg|300px]]
<br/>
Множество вершин красного цвета - — минимальное вершинное покрытие.
<br/>
<br/>
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
|proof=
Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания – — так, чтобы они шли из левой доли в правую. Запустим [[Обход_в_глубину,_цвета_вершин|обход в глубину]] из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода.Тогда <tex>L = L^+ \cup L^-</tex>, <tex>R = R^+ \cup R^-</tex>, где <tex>L, R</tex> – — правая и левая доли соответственно, <tex>L^+, R^+</tex> – — вершины правой и левой доли, посещенные обходом, <tex>L^-, R^-</tex> – — не посещенные обходом вершины.
Тогда в <tex>G</tex> могут быть следующие ребра:
[[Файл:bipartdfs_right.jpg|thumb|center|300px|Доли <tex>L^+, L^-, R^+, R^-</tex> и ребра между ними.]]
Очевидно, что ребер из <tex>L^+</tex> в <tex>R^-</tex> и из из <tex>R^+</tex> в <tex>L^-</tex> быть не может.
Ребер из из <tex>R^-</tex> в <tex>L^+</tex> быть не может, т.к. если такое ребро <tex>uv</tex> существует, то оно – — ребро паросочетания. Тогда вершина <tex>v</tex> насыщена паросочетанием. Но т.к. <tex>v \in L^+</tex>, то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро <tex>wv, w \in R^+</tex>. Но тогда <tex>v</tex> инцидентны два ребра из паросочетания. Противоречие.
Заметим, что минимальным вершинным покрытием <tex>G</tex> является либо <tex>L</tex>, либо <tex>R</tex>, либо <tex>L^- \cup R^+</tex>.
В <tex>R^+</tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетания.
В <tex>L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R^+</tex>
и <tex>L^-</tex> нет, то каждому ребру <tex>MM</tex> максимальным паросочетания инцидентна ровно одна вершина из <tex>L^- \cup R^+</tex>. Тогда <tex>|L^- \cup R^+| = |MM| \le \min(|L|, |R|)</tex>. Значит, минимальным вершинным покрытием является Множество вершин <tex>L^- \cup R^+</tex> и <tex>|MVC| = |MM|</tex>является минимальным вершинным покрытием. Значит максимальное паросочетание равно минимальному вершинному покрытию.
}}
===Алгоритм построения MVCминимального вершинного покрытия===
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
*Построить максимальное паросочетание.
*Ориентировать ребра:
**Из паросочетания – — из правой доли в левую.**Не из паросочетания – — из левой доли в правую.
*Запустить обход в глубину из всех свободных вершин левой доли, построить множества <tex>L^+,L^-,R^+,R^-,</tex>.
*В качестве результата взять <tex>L^- \cup R^+</tex>.
==См. также ==
[[Связь_вершинного_покрытия_и_независимого_множества|Связь вершинного покрытия и независимого множества]].
== Источники ==
