Изменения

Пусть Обозначим как <tex>p'</tex> путь из <tex>s</tex> в <tex>t</tex> без первого и последнего ребра. Пусть онявляется дополняющей цепью для исходного графа <tex>G</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы]] - если мы на каждом шаге можем найти новый путь, т.е. находим новую дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, то текущее паросочетание - искомое. Осталось доказать, что путь из <tex>s</tex> в <tex>tp'</tex> действительно является дополняющей цепью.

В этом пути два конца свободны, тТ.к. они не являются ребрами графа <tex>Gp'</tex> и- путь в двудольном графе, значитон нечетной длины, в котором вершины не входят в паросочетание. По построению графа <tex>G'</tex> этот путь содержит нечетное число ребер повторяются (т.к. этот путь строится с помощью поиска в <tex>G'</tex> нет ребер из <tex>s</tex> в <tex>y \in R</tex>глубину). В таком случае его ребра можно пронумеровать так, чтобы нечетные ребра были свободными, а так же ребер четные - покрытыми, т.е. только ребра из <tex>x \in L</tex> в <tex>t</tex>, то попасть из истока в сток можно только через какие-либо две вершины <tex>x \in L</tex> и <tex>y \in R</tex>, расстояние между которыми включаем в двудольном графе паросочетание(в ребрахчто соответствует инварианту его построения) - нечетная величина). В таком случае ребра пути <tex>s-t</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные - покрытыми. Тогда этот путь - дополняющая цепь для графа <tex>G</tex>, алгоритм корректен.