80
правок
Изменения
→Идея алгоритма
<tex>E' = \{(s, u): u \in L\} \cup \{(u, v): u \in L, v \in R\ , (u, v) \in E\} \cup \{(v, t): v \in R\} </tex>.
Изначально максимальное паросочетание пусто. На каждом шаге алгоритма в него входят ребра, ведущие из <tex>RL</tex> в <tex>LR</tex>.
# Ищем в графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.
# Если путь найден, перезаписываем текущее паросочетание. Теперь инвертируем все рёбра на пути (ребро <tex>(u, v)</tex> становится ребром <tex>(v, u)</tex> ). После этого перезаписываем текущее паросочетаниеи удаляем <tex>(s, L)</tex> и <tex>(R, t)</tex> ребра, покрывающие вершины, принадлежащие текущему паросочетанию.
# Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.
