Изменения

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

* Граф <tex>G\langle V, E \rangle</tex> хранится списками в матрице смежности <tex>g[vi][ij]</tex>* Функция <tex>dfs(v)</tex> {{---}} обход в глубину, возвращает размера <tex>truen </tex> если есть увеличивающая цепь из вершины на <tex>vn</tex>.* В массиве <tex>matching</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, matching[i])n = |V|</tex>. 

'''bool''' '''dfs'''(v: '''int''' v) :

'''return ''' ''false'' used[v] = ''true;'' '''for''' to '''in''' g[v]: '''if ''' (matching[to] == -1 || '''or''' dfs(matching[to])):

'''return''''' true '' '''return''''' false''

function '''main'''(): fill(matching, -1) '''for''' u i = 1..n fill(used, ''false'in''' N:) fill dfs(used, falsei) '''dfsfor'''(u)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> — число вершин второй доли.

==Источникиинформации==