Изменения

Если из вершины <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>MP</tex> принадлежит паросочетанию <tex>M'</tex>, тогда <tex>NP</tex> ему не принадлежит.<br>:: (Случай, когда <tex>NP</tex> принадлежит паросочетанию <tex>M'</tex> полностью симметричен.)<br><br>

: Кроме того, ребро <tex>QP</tex> не лежит ни в исходном паросочетании <tex>M</tex>, ни в паросочетании <tex>M'</tex>, в противном случае оказалось бы, что вершина <tex>p</tex> инцидентна нескольким ребрам рёбрам из паросочетания, что противоречит определению паросочетания.<br><br>

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

:Краткое описание алгоритма:В массиве <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>v\mathtt{matching}</tex> первой доли графа заполняется числами <tex>v = -1 ... n_1</tex>::*Если текущая ). Затем перебирается вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем:*Иначе — алгоритм пытается насытить эту вершину<tex>v </tex>, для чего и из неё запускается поиск увеличивающей цепиобход в глубину <tex> \mathrm{dfs} </tex>, начинающейся с этой вершиныпредварительно обнулив массив <tex> used</tex>.

: Этот обход* Граф <tex>G\langle V, запущенный из вершины E \rangle</tex>vхранится в матрице смежности <tex>g[i][j]</tex>, либо найдёт увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина размера <tex>n </tex> на <tex>n</tex>*<tex>n уже не сможет стать насыщенной).= |V|</tex>

'''bool''' dfs(v: После того, как все вершины <tex>'''int'''): '''if''' (used[v ]) '''return''' ''false'' used[v] = ''true'' '''for''' to '''in''' g[v] '''if''' (matching[to] == -1 ... n_1</tex> будут просмотрены, текущее паросочетание будет максимальным.'''or''' dfs(matching[to])): matching[to] = v '''return''' ''true'' '''return''' ''false''

function '''main'''(): Граф <tex>G</tex> хранится списками смежности <tex>g[][]</tex>: Функция <tex> fill(matching, -1) '''for''' i = 1..n fill(used, ''false'') dfs(vi)</tex> '''for''' i = 1..n '''if''' (matching[i] != - обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>.1): В массиве <tex>mt</tex> хранятся паросочетания. Паросочетание есть ребро <tex> print(i, mt" ", matching[i])</tex>.

bool dfs(int v) { if (used[v]) return false; used[v] = true; for (int i = 0; i < g[v].size(); i++) { int to Ссылки= g[v][i]; if (mt[to] == -1 || dfs(mt[to])) { mt[to] = v; return true; } } return false; } int main() { ... чтение графа ... mt.assign (k, -1); for (int v = 0; v < n; v++) { used.assign(n, false); dfs(v); } for (int i = 0; i < k; i++) if (mt[i] != -1) ... вывод ... }

==Время работы==* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]:Итак, алгоритм Куна можно представить как серию из * [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|<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 стр.