Изменения

[[Файл: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><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> не существует дополняющей цепи.

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

3) Если :Краткое описание алгоритма::* Возьмём пустое паросочетание:* Пока в графе удаётся найти увеличивающую цепь найдена, инвертируем все ребра на выполняем чередование паросочетания вдоль этой цепи:* Повторяем процесс поиска увеличивающей цепи. :* Если увеличивающую цепь найти не удалось — процесс останавливается:* Найденное паросочетание и является максимальным.

:Будем считать, что граф уже разбит на две доли.:Просматриваем все вершины <tex>v</tex> первой доли графа <tex>v ==Псевдокод==1 ... n_1</tex>::*Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем:*Иначе — алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.

bool :Рассмотрим поиск увеличивающей цепи обходом в глубину.:* Изначально обход в глубину стоит в текущей ненасыщенной вершине <tex>v</tex> первой доли.:* Просматриваем все рёбра из этой вершины, пусть текущее ребро — <tex>(v, t_0)</tex>.:* Если вершина '''dfs'''ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра <tex>(v, t_0)</tex>.:** Включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины <tex>v</tex>.:** Иначе, — если уже насыщена каким-то ребром <tex>(p, t_0)</tex>, то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра <tex>(v, t_0), (t_0, p)</tex>. Для этого просто перейдём в нашем обходе в вершину <tex>p</tex>.:*** Пробуем найти увеличивающую цепь из вершины <tex>p</tex>. : Этот обход, запущенный из вершины <tex>v</tex>, либо найдёт увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (xи, следовательно, эта вершина уже не сможет стать насыщенной). :После того, как все вершины <tex>v = 1 ... n_1</tex> будут просмотрены, текущее паросочетание будет максимальным. vis==Релизация== : Граф <tex>G</tex> хранится списками смежности <tex>g[x] = []</tex>: Функция <tex>dfs(v)</tex> - обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>. '''for''' : В массиве <tex>mt</tex> хранятся паросочетания. Паросочетание есть ребро <tex>xy \in E(i, mt[i])</tex>:.   bool dfs(int v) { if (used[v]) return false; used[v] = true; for (int i = 0; i < g[v].size(); i++) { k int to = pyg[v][yi]; ''' if''' (k mt[to] == -1) or || dfs(('''not''' vismt[kto]) '''and''' ('''dfs'''(k))): py { mt[yto] = xv; return true; } } return false; } Kuhn int main(): py[] = { ... чтение графа ... mt.assign (k, -1); ''' for''' (int v = 0; v <tex>s \in Ln; v++) { used.assign(n, false); dfs(v); } for (int i = 0; i </tex>:k; i++) vis if (mt[i] != false-1) ... вывод ... '''dfs'''(s) }

:Итак, алгоритм Куна можно представить как серию из |<tex>L</tex>| запусков обхода в глубину на всём графе. :Следовательно, всего этот алгоритм исполняется за время <tex>O(V E)</tex>, что в худшем случае есть <tex>O(V^3)</tex>.

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