Изменения

Задан граф <tex>G(V, E)</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем Алгоритм можно описать так:Алгоритм просматривает все вершины графа по очередисначала возьмём пустое паросочетание, запуская из каждой обход (в глубину или а потом — пока в ширину), пытающийся графе удаётся найти увеличивающую цепь, начинающуюся в — будем выполнять чередование паросочетания вдоль этой вершинецепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось — процесс останавливаем, — текущее паросочетание и есть максимальное.:Задан двудольный граф В массиве <tex>matching</tex> хранятся паросочетания <tex>G(Vv, Ematching[v])</tex> (Если паросочетания с вершиной <tex> v </tex> не существует, где то <tex>V_1matching[v] </tex> и = -1). А <tex>V_2used</tex> {{---}} его левая и правая доли соответственнообычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды). :Просматриваем все вершины Функция <tex>v\mathrm{dfs} </tex> первой доли графа возвращает <tex>u \in V_1true</tex>::*Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное , если ей ребро), то эту вершину пропускаем;:*Иначе запускаем поиск увеличивающей цепи, начинающейся с этой вершины.:Рассмотрим поиск увеличивающей цепи обходом в глубину.:* Запускаем обход от удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.:* Просматриваем Внутри функции просматриваются все рёбра , исходящие из этой вершиныv первой доли, пусть текущее и затем проверяется: если это ребро — ведёт в ненасыщенную вершину <tex>(v, to)</tex>.:* Если , либо если эта вершина <tex>to</tex> ещё не насыщена паросочетанием, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>mt[to]</tex>, то включаем мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро , смежное с <tex>(v, to)</tex> , в паросочетание и прекращаем поиск из вершины вершину <tex>v</tex>.:* ИначеВ основной программе сначала указывается, если вершина что текущее паросочетание — пустое (список <tex>tomt</tex> уже насыщена какимзаполняется числами -то ребром 1). Затем перебирается вершина <tex>(p, to)v </tex> первой доли, и не посещена, то просто перейдем из неё запускается обход в нашем обходе в вершину глубину <tex>p\mathrm{dfs} </tex>.:** Пробуем найти часть увеличивающей цепи из вершины , предварительно обнулив массив <tex>pused</tex>.:** Если получилосьСтоит заметить, то удаляем из что размер паросочетания ребро легко получить как число вызовов <tex>(p, to)\mathrm{dfs} </tex>в основной программе, а вместо него добавляем вернувших результат <tex>(v, to)true </tex>: Этот обход, запущенный из вершины . Само искомое максимальное паросочетание содержится в массиве <tex>vmt </tex>, либо найдет увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина уже не сможет стать насыщенной).: После того, как все вершины <tex>u v \in V_1V</tex> будут просмотрены, текущее паросочетание будет максимальным.: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>