Изменения
→Алгоритм
==Алгоритм==
Пусть дан двудольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. <br>
1) Будем искать путь из Просматриваем вершины <tex>s</tex> в из доли <tex>tL</tex> поиском в глубину.
2) Если путь найден, инвертируем все ребра на путиБудем искать дополняющую цепь из <tex>s</tex> поиском в глубину.
3) Если путь не был найденцепь найдена, значит текущее паросочетание является максимальным и алгоритм завершает работуинвертируем все ребра на этой цепи. Иначе переходим к пункту 1)
В любой момент времени текущим паросочетанием будет множество ребер, направленных из <tex>R</tex> в <tex>L</tex>. Корректность работы алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]] и доказанной выше теоремы.
