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