147
правок
Изменения
м
Нет описания правки
:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра <tex>(v, to)</tex>.
:** Включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины <tex>v</tex>.
:* Иначе, если вершина <tex>to</tex> уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра <tex>(v, to), (to, p)</tex>. Для этого просто перейдем в нашем обходе в вершину <tex>p</tex>.
:** Пробуем найти увеличивающую цепь из вершины <tex>p</tex>.
:** Если цепь существует, то удаляем из паросочетания ребро <tex>(p, to)</tex>, а вместо него добавляем <tex>(p, v)</tex>
