Изменения

Если из вершины <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> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v] = -1</tex> = -1). А <tex>used</tex> - — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).

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

В основной программе сначала указывается, что текущее паросочетание — пустое (список массив <tex> mt\mathtt{matching}</tex> заполняется числами <tex>-1</tex>). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> mt \mathtt{matching}</tex>.

* Граф <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'''): '''if''' (used[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''' v '''in''' V:i = 1..n fill(used, '''false''') '''dfs'''(vi) '''for''' v '''in''' V:i = 1..n '''if''' (matching[vi] != -1): '''print'''(vi, " ", matching[vi])

:Итак, алгоритм Куна можно представить как серию из <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> — число вершин второй доли.

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