Изменения
Нет описания правки
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
|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> могут быть следующие ребра:
*Из вершин <tex>L^+</tex> в вершины <tex>R^+</tex> и из вершин <tex>R^+</tex> в вершины <tex>L^+</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>.
