Изменения
→Алгоритм
:Краткое описание алгоритма:
:* Возьмём пустое паросочетание.;:* Разобьем граф на две доли.;:* Проходя по всем вершинам первой доли пытаемся найти увеличивающую цепь с началом в текущей вершине.;
::* Если удается найти увеличивающую цепь, выполняем чередование паросочетания вдоль этой цепи.
:* Найденное паросочетание и является максимальным.
:Будем считать, что граф уже разбит на две доли.
:Просматриваем все вершины <tex>v</tex> первой доли графа <tex>v = 1 ... n_1</tex>:
:*Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем;:*Иначе — алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.
:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра <tex>(v, to)</tex>.
:** Включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины <tex>v</tex>.
:* Иначе, — если уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра <tex>(v, t_0), (t_0, p)</tex>. Для этого просто перейдем в нашем обходе в вершину <tex>p</tex>.
:** Пробуем найти увеличивающую цепь из вершины <tex>p</tex>.
