80
правок
Изменения
→Корректность алгоритма
==Корректность алгоритма==
# Путь из <tex>s</tex> в <tex>t</tex> является [[Теорема о максимальном паросочетании и дополняющих цепях|дополняющей цепью ]] для исходного графа <tex>G</tex>. Действительно, в этом пути два конца свободны, т.к. они не являются ребрами графа <tex>G</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>R</tex> в <tex>L</tex> является паросочетанием.
