Изменения

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

: Пусть <tex>p</tex> &#8211; – ближайшая к <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 \rangle</tex>, про который известно, что он двудольный, пытающийся но разбиение не задано явно. Требуется найти увеличивающую цепь, начинающуюся наибольшее паросочетание в этой вершине.нём

:Задан граф В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex>G(Vv, E\mathtt{matching}[v])</tex>, где (Если паросочетания с вершиной <tex>V = V_1 + V_2v </tex> и не существует, то <tex>V_1 \cap V_2 mathtt{matching}[v]= \varnothing-1</tex>). :Просматриваем все вершины А <tex>vused</tex> первой доли графа — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).Функция <tex>u \in V_1mathrm{dfs} </tex>::*Если текущая вершина возвращает уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное <tex>true</tex>, если ей ребро)удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, то эту вершину пропускаем;:*Иначе запускаем поиск увеличивающей что эта функция уже произвела чередование паросочетания вдоль найденной цепи, начинающейся с этой вершины.

:Рассмотрим поиск увеличивающей цепи обходом в глубину.:* Запускаем обход от вершины <tex>v</tex>.:* Просматриваем все рёбра из этой вершиныВ основной программе сначала указывается, пусть что текущее ребро паросочетание — пустое (массив <tex>(v, to)\mathtt{matching}</tex>.:* Если вершина заполняется числами <tex>to-1</tex> ещё не насыщена паросочетанием, то включаем ребро <tex>(v, to)</tex> в паросочетание и прекращаем поиск из вершины <tex>v</tex>.:* Иначе, если Затем перебирается вершина <tex>tov </tex> уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то просто перейдем из неё запускается обход в нашем обходе в вершину глубину <tex>p\mathrm{dfs} </tex>.:** Пробуем найти часть увеличивающей цепи из вершины , предварительно обнулив массив <tex>pused</tex>.:** Если получилось, то удаляем из паросочетания ребро <tex>(p, to)</tex>, а вместо него добавляем <tex>(v, to)</tex>

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

: После того, как все вершины * Граф <tex>u G\in V_1langle V, E \rangle</tex> будут просмотрены, текущее паросочетание будет максимальным.: Корректность алгоритма следует из хранится в матрице смежности <tex>g[i][Теорема о максимальном паросочетании и дополняющих цепяхj]</tex> размера <tex>n </tex> на <tex>n</tex>*<tex>n = |V|теоремы Бержа]] и теоремы, описанной выше.<br/tex>

'''bool''' dfs(v: '''int'''): '''if''' (used[v]) '''return''' ''false'' used[v] =''true'' '''for''' to '''in''' g[v] '''if''' (matching[to] =Релизация=-1 '''or''' dfs(matching[to])): matching[to] =v '''return''' ''true'' '''return''' ''false''

  bool dfsfunction '''main'''(int v) {: if fill(used[v]matching, -1) return false; used[v] = true; '''for (int ''' i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (mt[to] == -1 || dfs(mt[to])) { mt[to] = v; return true; } } return false; } int main() { ... чтение графа ...n mt.assign fill(k, -1); for (int v = 0; v < n; v++) { used.assign(n, ''false''); dfs(vi); } '''for (int ''' i = 0; i < k; i++)1..n '''if ''' (mtmatching[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 стр.