80
правок
Изменения
м
→Корректность алгоритма
является дополняющей цепью для исходного графа <tex>G</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы]] - если мы на каждом шаге можем найти новый путь, т.е. находим новую дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, то текущее паросочетание - искомое. Осталось доказать, что путь <tex>p'</tex> действительно является дополняющей цепью.
Т.к. <tex>p'</tex> - путь в двудольном графе, он нечетной длины, в котором вершины не повторяются (т.к. этот путь строится с помощью поиска в глубину). В таком случае его ребра можно пронумеровать так, чтобы нечетные ребра были свободными, а четные - покрытыми, т.е. только ребра из <tex>L</tex> в <tex>R</tex> включаем в паросочетание(что соответствует инварианту его построения). Тогда этот путь - дополняющая цепь для графа <tex>G</tex>, алгоритм корректен.
==Оценка производительности==
