Изменения

Если из вершины <tex>x</tex> не существует [[Теорема о максимальном паросочетании и дополняющих цепях|дополняющей цепи ]] относительно паросочетания <tex>M</tex> и паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи, тогда из <tex>x</tex> не существует дополняющей цепи в <tex>M'</tex>.

: Пусть <tex>p</tex> {{---}} – ближайшая к <tex>x</tex> вершина, которая принадлежит и новой дополняющей цепи и цепи <tex>(y \rightsquigarrow z)</tex>.: Тогда <tex>MP</tex> - – последнее ребро на отрезке <tex>(y \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>NP</tex> - – последнее ребро на отрезке <tex>(z \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>QP</tex> - последнее ребро лежащее на отрезке <tex>(x \rightsquigarrow p)</tex> новой дополняющей цепи(см. Рисунок 1).<br><br>

: Кроме того, ребро <tex>QP</tex> не лежит ни в исходном паросочетании <tex>M</tex>, ни в паросочетании <tex>M'</tex>, в противном случае оказалось бы, что вершина <tex>p</tex> инцидентна нескольким ребрам рёбрам из паросочетания, что противоречит определению паросочетания.<br><br>

:Алгоритм просматривает все вершины графа по очереди, запуская из каждой обход (в глубину или в ширину), пытающийся найти увеличивающую цепь, начинающуюся в этой вершине.:Задан двудольный граф <tex>G(\langle V, E)</tex>, где <tex>V_1</tex> и <tex>V_2</tex> {{---}} его левая и правая доли соответственно. :Просматриваем все вершины <tex>v</tex> первой доли графа <tex>u \in V_1rangle</tex>::*Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем;:*Иначе запускаем поиск увеличивающей цепипро который известно, начинающейся с этой вершины.:Рассмотрим поиск увеличивающей цепи обходом в глубину.:* Запускаем обход от вершины <tex>v</tex>.:* Просматриваем все рёбра из этой вершинычто он двудольный, пусть текущее ребро — <tex>(v, to)</tex>но разбиение не задано явно.:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то включаем ребро <tex>(v, to)</tex> в Требуется найти наибольшее паросочетание и прекращаем поиск из вершины <tex>v</tex>.:* Иначе, если вершина <tex>to</tex> уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то просто перейдем в нашем обходе в вершину <tex>p</tex>.:** Пробуем найти часть увеличивающей цепи из вершины <tex>p</tex>.:** Если получилось, то удаляем из паросочетания ребро <tex>(p, to)</tex>, а вместо него добавляем <tex>(v, to)</tex>нём

Алгоритм можно описать так: Этот обходсначала возьмём пустое паросочетание, запущенный из вершины <tex>v</tex>, либо найдет а потом — пока в графе удаётся найти увеличивающую цепь, — будем выполнять чередование паросочетания вдоль этой цепи, и тем самым насытит вершину, либо же такой повторять процесс поиска увеличивающей цепи . Как только такую цепь найти не найдёт (удалось — процесс останавливаем, — текущее паросочетание и, следовательно, эта вершина уже не сможет стать насыщенной)есть максимальное.

: После тогоВнутри функции просматриваются все рёбра, как все исходящие из вершины <tex>u \in V_1v</tex> будут просмотрены, текущее паросочетание будет максимальным.и затем проверяется: Корректность алгоритма следует если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]to] </tex>, то мы говорим, что мы нашли увеличивающую цепь, и теоремыперед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, описанной выше.в вершину <brtex>v</tex>.

: Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>: Функция Стоит заметить, что размер паросочетания легко получить как число вызовов <tex>\mathrm{dfs(v)} </tex> {{---}} обход в глубинуосновной программе, возвращает вернувших результат <tex>true</tex> если есть увеличивающая цепь из вершины . Само искомое максимальное паросочетание содержится в массиве <tex>v\mathtt{matching}</tex>.: В массиве После того, как все вершины <tex>matchingv \in V</tex> хранятся паросочетаниябудут просмотрены, текущее паросочетание будет максимальным. Паросочетание есть ребро <tex>(i, matchingКорректность алгоритма следует из [[iТеорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]])и теоремы, описанной выше.</texbr>.

* Граф <tex>G\langle V, E \rangle</tex> хранится в матрице смежности <tex>g[i][j]</tex> размера <tex>n </tex> на <tex>n</tex>*<tex>n = |V|</tex>  '''bool ''' dfs(v: '''int v''') {: '''if ''' (used[v]) '''return ''' ''false; '' used[v] = ''true;'' '''for (int i = 0; i < g[v].size(); i++) { int ''' to = '''in''' g[v][i]; '''if ''' (matching[to] == -1 || '''or''' dfs(matching[to])) {: matching[to] = v; '''return ''' ''true; } }'' '''return ''' ''false;'' } int function '''main'''() { ... чтение графа ...: fill(matching.assign (k, -1); '''for (int u ''' i = 0; u < 1..n; u++) { fill(used.assign(n, ''false''); dfs(ui); } '''for (int ''' i = 0; i < k; i++)1..n '''if ''' (matching[i] != -1) ... вывод ... } print(i, " ", matching[i])

:Итак, алгоритм Куна можно представить как серию из <tex>n_1n</tex> запусков обхода в глубину на всём графе.:Следовательно, всего этот алгоритм исполняется за время <tex>O(nm)</tex>, где <tex>m</tex> {{---}} количество реберрёбер, что в худшем случае есть <tex>O(n^3)</tex>.:Более точная оценка::В описанной выше реализации запуски обхода в глубинуЕсли явно задано разбиение графа на две доли размером <tex>n_1</tex> и <tex>n_2</tex>, то можно запускать <tex>\mathtt{dfs}</ширину происходят tex> только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1m)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2).</tex>, где <tex>n_2</tex> — число вершин второй доли.

==Источникиинформации==:*[http://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания]<br>: * Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.