Изменения
Нет описания правки
<br/>
==Связь MM максимального паросочетания и MVC минимального вершинного покрытия в двудольном графе=====Максимальное паросочетание==={{Определение|definition='''Максимальным''' [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|'''паросочетанием''']] (англ. '''Maximum matching''', '''MM''') в [[Двудольные графы и раскраска в 2 цвета|двудольном графе]] <tex>G</tex> называется паросочетание максимальной мощности.}}===Теорема о мощности MVC минимального вершинного покрытия и MMмаксимального паросочетания===
{{Теорема|neat = neat|statement=
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
В <tex>L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R^+</tex>
и <tex>L^-</tex> нет, то каждому ребру максимальным паросочетания инцидентна ровно одна вершина из <tex>L^- \cup R^+</tex>.
Тогда <tex>|L^- \cup R^+| = |MM|</tex>. Множество вершин <tex>L^- \cup R^+</tex> является минимальным вершинным покрытием. Значит максимальное паросочетание равно минимальному вершинному покрытиюмощность максимального паросочетания равна мощности минимального вершинного покрытия.
}}
