Изменения

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

[[Файл:Kuhn2.png|thumb|right|300x300px|Рисунок 1.]][[Файл:Kuhn1.png|thumb|leftright|300x300px|Рисунок 2.<br>Пунктиром обозначен путь между двумя вершинами. Ребро красного цвета лежит в паросочетании, а черного - нет.]][[Файл:Kuhn2.png|thumb|right|300x300px|]]Доказательство от противного. <br><br>: Допустим в паросочетание внесли изменения вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex> и из вершины <tex>x</tex> появилась дополняющая цепь. : Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из <tex>x</tex> существовала и в исходном паросочетании. <br><br>: Пусть <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>MP</tex> принадлежит паросочетанию <tex>M'</tex>, тогда <tex>NP</tex> ему не принадлежит. <br>:: (Случай, когда <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>L</tex> и <tex>R</tex>. <br>1) Просматриваем вершины <tex>s</tex> из доли <tex>L</tex>.

2) Будем искать дополняющую Алгоритм можно описать так: сначала возьмём пустое паросочетание, а потом — пока в графе удаётся найти увеличивающую цепь, — будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь из <tex>s</tex> (напримернайти не удалось — процесс останавливаем, поиском в глубину)— текущее паросочетание и есть максимальное.

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

В любой момент времени текущим паросочетанием будет множество реберВнутри функции просматриваются все рёбра, направленных исходящие из вершины <tex>Rv</tex> , и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex>Lto</tex>. Корректность работы алгоритма следует , либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]to] </tex>, то мы говорим, что мы нашли увеличивающую цепь, и доказанной выше теоремыперед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</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'''(x): vis '''if''' (used[xv] = true) '''return''''for'false'' <tex>xy \in E</tex>: k = py used[yv]= ''true'' '''iffor''' (k == -1) or ((to '''notin''' visg[kv]) '''andif''' (matching[to] == -1 '''dfsor'''dfs(k)matching[to])): py matching[yto] = xv '''return ''' ''true'' '''return ''' ''false''   Kuhn function '''main'''(): py[] = fill(matching, -1) '''for''' <tex>s \in L</tex>:i = 1..n fill(used, ''false'') dfs(i) vis[] '''for''' i = false1..n '''dfsif'''(smatching[i] != -1) print(i, " ", matching[i])

:Итак, алгоритм Куна можно представить как серию из |<tex>Ln</tex>| запусков обхода в глубину на всём графе. :Следовательно, всего этот алгоритм исполняется за время <tex>O(V Enm)</tex>, где <tex>m</tex> {{---}} количество рёбер, что в худшем случае есть <tex>O(Vn^3)</tex>:Если явно задано разбиение графа на две доли размером <tex>n_1</tex> и <tex>n_2</tex>, то можно запускать <tex>\mathtt{dfs}</tex> только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1m)</tex>. В худшем случае это составляет <tex>O(n_1^2n_2).</tex> ==Ссылки== * [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]

==Источникиинформации==*[http://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания]<br>* Асанов М., Баранский В., Расин В. {{--- }} Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.