80
правок
Изменения
→Идея алгоритма
<tex>V' = V \cup \{s, t\}</tex> (т.е. добавим новый исток <tex>s</tex> и сток <tex>t</tex>);
<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>R</tex> в <tex>L</tex>.
