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\} \cup \{(v, t): v \in R\} </tex> (проведем ребра из <tex>s</tex> в каждую вершину <tex>L</tex>, из каждой вершины <tex>R</tex> в <tex>t</tex>, и ориентируем все ребра графа <tex>G'</tex> так, чтобы они шли от <tex>u \in L\</tex> к <tex>v \in R\</tex>).
Изначально максимальное паросочетание пусто.
