Изменения

Если из вершины х <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.]][[Файл:Kuhn1.png|thumb|right|300x300px|Рисунок 2.<br>Пунктиром обозначен путь между двумя вершинами. Ребро красного цвета лежит в паросочетании, а черного - нет.]]: Доказательство от противного! .<br><br>: Допустим, что из х появилась дополняющая цепь относительно M'. Рассмотрим в паросочетание внесли изменения, которые мы внесли в М вдоль дополняющей цепи, чтобы получить паросочетание М'. В этой цепи все промежуточные <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>\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</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>L\mathrm{dfs} </tex> и в основной программе, вернувших результат <tex>Rtrue </tex>. Само искомое максимальное паросочетание содержится в массиве <brtex> \mathtt{matching}</tex>.1) Просматриваем После того, как все вершины <tex>sv \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.Корректность алгоритма следует из доли [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br> ==Реализация== * Граф <tex>G\langle V, E \rangle</tex> хранится в матрице смежности <tex>Lg[i][j]</tex>.размера <tex>n </tex> на <tex>n</tex>*<tex>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])): matching[to] = v '''return''' ''true'' '''return''' ''false'' 

2 function '''main'''() Будем искать дополняющую цепь из <tex>s</tex> поиском в глубину: fill(matching, -1) '''for''' i = 1..n fill(used, ''false'') dfs(i) '''for''' i = 1.. n '''if''' (matching[i] != -1) print(i, " ", matching[i])

==Время работы==:Итак, алгоритм Куна можно представить как серию из <tex>n</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>O(n_1^2n_2).</tex>

bool '''dfs'''(x):==Источники информации== vis*[xhttp://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания] = true '''for''' <tex>xy \in E</texbr>* Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — СПб.:Издательство "Лань", 2010. — 291 стр. k = py[y[Категория: Алгоритмы и структуры данных]] '''if''' (k == -1) or (('''not''' vis[k]) '''and''' ('''dfs'''(k))): py[y] = x return true return false Kuhn()Категория: py[Задача о паросочетании] = -1 '''for''' <tex>s \in L</tex>: vis[] = false '''dfs'''(s)