Изменения
Нет описания правки
|proof=
Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания --- так, чтобы они шли из левой доли в правую. Запустим обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода.
Тогда <tex>L = L_L^+ \cup L_L^-</tex>, <tex>R = R_R^+ \cup R_R^-</tex>, где <tex>L, R</tex> --- правая и левая доли соответственно, <tex>L_L^+, R_R^+</tex> --- вершины правой и левой доли, посещенные обходом, <tex>L_L^-, R_R^-</tex> --- не посещенные обходом вершины.
Тогда в <tex>G</tex> могут быть следующие ребра:
*Из вершин <tex>L_L^+</tex> в вершины <tex>R_R^+</tex> и из вершин <tex>R_R^+</tex> в вершины <tex>L_L^+</tex>.*Из вершин <tex>L_L^-</tex> в вершины <tex>R_R^-</tex> и из вершин <tex>R_R^-</tex> в вершины <tex>L_L^-</tex>. *Из вершин <tex>L_L^-</tex> в вершины <tex>R_R^+</tex>.
Очевидно, что ребер из <tex>L_L^+</tex> в <tex>R_R^-</tex> и из из <tex>R_R^+</tex> в <tex>L_L^-</tex> быть не может.Ребер из из <tex>R_R^-</tex> в <tex>L_L^+</tex> быть не может, т.к. если такое ребро <tex>uv</tex> существует, то оно --- ребро паросочетания. Тогда вершина <tex>v</tex> насыщена паросочетанием. Но т.к. <tex>v \in L_L^+</tex>, то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро <tex>wv, w \in R_R^+</tex>. Но тогда <tex>v</tex> инцидентны два ребра из паросочетания. Противоречие.
Заметим, что минимальным вершинным покрытием <tex>G</tex> является либо <tex>L</tex>, либо <tex>R</tex>, либо <tex>L_L^- \cup R_R^+</tex>.В <tex>R_R^+</tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетания.В <tex>L_L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L_L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R_R^+</tex>и <tex>L_L^-</tex> нет, то каждому ребру <tex>MM</tex> инцидентна ровно одна вершина из <tex>L_L^- \cup R_R^+</tex>.
Тогда <tex>|L_L^- \cup R_R^+| = |MM| \le min(|L|, |R|)</tex>. Значит, <tex>|MVC| = |MM|</tex>.
}}
[[Файл:Matching.jpg|thumb|right|Пример максимального паросочетания]]
