Изменения

Если из вершины <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_1</tex> будут просмотрены, текущее наибольшее паросочетание будет максимальным.: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>в нём

: Граф В массиве <tex>G\mathtt{matching}</tex> хранится списками смежности хранятся паросочетания <tex>g(v, \mathtt{matching}[v][i]) </tex>: Функция (Если паросочетания с вершиной <tex>dfs(v)</tex> {{---}} обход в глубинуне существует, возвращает то <tex>true\mathtt{matching}[v]= -1</tex> если есть увеличивающая цепь из вершины ). А <tex>vused</tex>— обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).: В массиве Функция <tex>matching\mathrm{dfs} </tex> хранятся паросочетания. Паросочетание есть ребро возвращает <tex>true</tex>(i, matching[i])если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами <tex>-1</tex>). Затем перебирается вершина <tex>v </tex>, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>. Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br> ==Реализация== * Граф <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 стр.