105
правок
Изменения
Нет описания правки
==Определения==
{{Определение|definition=
Паросочетанием <tex>M</tex> <tex>(matching)</tex> в графе <tex>G</tex> называется такое подмножество множества ребер графа <tex>Е</tex>,
максимальной мощности.
}}
{{Определение|definition=
Вершинным покрытием <tex>VC</tex> <tex>(vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется такое подмножество множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex><br/> инцидентна хотя бы одна вершина из <tex>VC</tex>.
==Связь MM и MVC в двудольном графе==
===Теорема о мощности MVC и MM===
{{Теорема|statement=
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
Тогда <tex>|L^- \cup R^+| = |MM| \le min(|L|, |R|)</tex>. Значит, <tex>|MVC| = |MM|</tex>.
}}
===Алгоритм поиска MVC===Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:*Построить максимальное паросочетание.*Ориентировать ребра:**Из паросочетания – из правой доли в левую.**Не из паросочетания – из левой доли в правую.*Запустить обход в глубину из всех свободных вершин левой доли, построить множества <tex>L^+,L^-,R^+,R^-,</tex>.*В качестве результата взять <tex>L^- \cup R^+</tex>.== Примеры ==<div class="tleft" style="clear:none">[[Файл:Matching.jpg|thumb|rightleft|Пример максимального паросочетания]]</div><div class="tleft" style="clear:none">[[Файл:Cover.jpg|thumb|left|Пример минимального вершинного покрытия]]</div>
