105
правок
Изменения
м
→Алгоритм
{{Теорема
|statement=
Если из вершины <tex>x</tex> не существует Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|дополняющей цепи]] относительно паросочетания <tex>M</tex> и паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи, тогда из <tex>x</tex> не существует дополняющей цепи в <tex>M'</tex>.
|proof=
[[Файл:Kuhn2.png|thumb|right|300x300px|Рисунок 1.]]
:: (Случай, когда <tex>NP</tex> принадлежит паросочетанию <tex>M'</tex> полностью симметричен.)<br><br>
: Поскольку паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex>, в паросочетание <tex>M</tex> входило ребро <tex>NP</tex>, а ребро <tex>MP</tex> нет.
: Кроме того, ребро <tex>QP</tex> не лежит ни в исходном паросочетании <tex>M</tex>, ни в паросочетании <tex>M'</tex>, в противном случае оказалось бы, что вершина <tex>p</tex> инцидентна нескольким ребрам рёбрам из паросочетания, что противоречит определению паросочетания.<br><br>
:Тогда заметим, что цепь <tex>(x \rightsquigarrow z)</tex>, полученная объединением цепей <tex>(x \rightsquigarrow p)</tex> и <tex>(p \rightsquigarrow z)</tex>, по определению будет дополняющей в паросочетании <tex>M</tex>, что приводит к противоречию, поскольку в паросочетании <tex>M</tex> из вершины <tex>x</tex> не существует дополняющей цепи.
}}
==Алгоритм==
Задан граф <tex>G\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в немнём
Алгоритм можно описать так: сначала возьмём пустое паросочетание, а потом — пока в графе удаётся найти увеличивающую цепь, — будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось — процесс останавливаем, — текущее паросочетание и есть максимальное.
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.
Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <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>G\langle V, E \rangle</tex> хранится в матрице смежности <tex>g[Ii][j]</tex> размера <tex>n </tex> на <tex>n</tex>*<tex>n = |V|</tex>
'''bool''' dfs(v: '''int'''):
function '''main'''():
fill(matching, -1)
'''for''' v '''in''' Vi = 1..n
fill(used, ''false'')
dfs(vi) '''for''' v '''in''' Vi = 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> — число вершин второй доли.
==Ссылки==
