Изменения

==АлгоритмИдея алгоритма==Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Преобразуем его в Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:

<tex>V' = V \cup \{s, t\}</tex>(т.е. добавим две новые вершины <tex>s</tex> и <tex>t</tex>)

Обозначим доли исходного графа как <tex>L</tex> и <tex>R</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>s</tex> в <tex>t</tex> поиском в глубину.