Изменения
Исправление алгоритма(неправильный символ)
<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>.{|align=Алгоритм="center" |-valign="center" |[[Файл:GrafG.png|thumb|200px|Пример графа <tex>G</tex>.]]Пусть дан двудольный |[[Файл:GrafG2.png|thumb|200px|Соответствующий граф <tex>G(V'</tex>.]] |}Изначально текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в текущее найденное паросочетание входят те и только те ребра, E)которые направлены из <tex>R</tex> и требуется найти максимальное паросочетание в нём<tex>L</tex>. Преобразуем его # Ищем в граф графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</tex> [[Обход_в_глубину,_цвета_вершин|поиском в глубину]]. # Если путь найден, перезаписываем текущее паросочетание. Далее инвертируем все рёбра на пути (ребро <tex>(u, v)</tex> становится ребром <tex>(V'v, u)</tex> ) и удаляем <tex>(s, L)</tex> и <tex>(R, E't)</tex> следующим образом ребра, покрывающие вершины, принадлежащие текущему паросочетанию.# Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.
Поиск в глубину запускается от вершины <tex>s</tex> не более чем <tex>L</tex> раз, т.к. из <tex>s</tex> ведет ровно <tex>L</tex> ребер, и при каждом запуске одно из них инвертируется. Сам поиск работает за <tex>O(E)</tex>, каждая инвертация и перезапись паросочетания так же занимает <tex>O(E)</tex> времени. Тогда все время алгоритма ограничено <tex>O(VE)</tex>.
==Псевдокод==