105
правок
Изменения
→Теорема о мощности MVC и MM
==Связь MM и MVC в двудольном графе==
===Теорема о мощности MVC и MM===
{{Теорема|neat = neat|statement=
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
|proof=
Тогда <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.jpg|right|200px|Доли <tex>L^+, L^-, R^+, R^-</tex> и ребра между ними.]]
*Из вершин <tex>L^+</tex> в вершины <tex>R^+</tex> и из вершин <tex>R^+</tex> в вершины <tex>L^+</tex>.
*Из вершин <tex>L^-</tex> в вершины <tex>R^-</tex> и из вершин <tex>R^-</tex> в вершины <tex>L^-</tex>.
