Изменения

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

Т.к. <tex>p'</tex> — путь в двудольном графе, начинающийся в <tex>L</tex> и заканчивающийся в <tex>R</tex>, то он нечетной длины, . Вершины в котором вершины нем не повторяются (т.к. этот это путь строится с помощью в дереве поиска в глубину). Рассмотрим текущее паросочетание. Мы записывали в него ребра из Согласно поддерживаемому инварианту <tex>(R,L)</tex> -ребра в паросочетании, а <tex>(L,R)</tex>, но после этого инвертировали их. Значит, -ребра текущего паросочетания сейчас ведут из <tex>R</tex> в <tex>L</tex>{{---}} нет. В таком случае ребра пути <tex>p'</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми (ребрами текущего паросочетания. Заметим, что соответствует текущему паросочетанию)путь может начинаться и заканчиваться только в свободной вершине, т. к. из <tex>s</tex> ведут ребра только в свободные вершины и только из свободных вершин ведут ребра в <tex>t</tex>. Тогда этот путь Итак, теперь ясно, что <tex>p'</tex> — дополняющая цепь для графа <tex>G</tex>, и паросочетание можно перезаписать. Обратно — , пусть существует дополняющая цепь в графе <tex>G</tex> это путь нечетной длины . В одной из ориентаций она начинается в какой-то свободной вершине <tex>u \in L\</tex> и заканчивается в свободной вершине <tex>v \in R\</tex>. Он начинается Ребра поочередно то не лежат, то лежат в паросочетании, значит в какой-нашей ориентации эти ребра поочередно ориентированы то <tex>(L, R)</tex>, то вершине <tex>(R,L)</tex>. Заметим что эта ориентация совпадает с изначально рассматриваемой, а значит в нашем ориентированом графе существует путь из свободной вершины <tex>u \in L\</tex> и заканчивается в вершине свободную вершину <tex>v \in R\</tex> (поскольку концевые вершины этого пути должны быть свободны). Нo каждая свободная вершина из <tex>L</tex> связана ребром с <tex>s</tex> в графе <tex>G'</tex>, аналогично каждая свободная вершина из <tex>R</tex> связана ребром с <tex>t</tex>. Тогда любая дополняющая цепь Не сложно заметить, что, в графе таком случае, <tex>Gt</tex> является частью пути достижим из <tex>s</tex> , а значит в процессе поиска в глубину будет найден некий <tex>s \rightarrow t</tex> в графе <tex>G'</tex>, или, что то же самое, является путем путь <tex>p'</tex>. Отсюда следует, что алгоритм корректен Утверждение доказано.