Изменения

Перейти к: навигация, поиск
м
Алгоритм
{{Теорема
|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>(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(NP)</tex> принадлежит паросочетанию <tex>M'</tex>, тогда <tex>NP(MP)</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(MP)</tex>, а ребро <tex>MP(NP)</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>v = 1 ... n_1to</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>v\mathrm{dfs} </tex> первой доли.:* Просматриваем все рёбра из этой вершиныв основной программе, пусть текущее ребро — вернувших результат <tex>(v, to)true </tex>.:* Если вершина <tex>toСамо искомое максимальное паросочетание содержится в массиве </tex> ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра <tex>(v, to)\mathtt{matching}</tex>.:** Включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из После того, как все вершины <tex>v\in V</tex>будут просмотрены, текущее паросочетание будет максимальным.:* Иначе, — если уже насыщена каким-то ребром <tex>(p, to)</tex> Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и не посещенатеоремы, то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра <tex>(v, t_0), (t_0, p)</tex>описанной выше. Для этого просто перейдем в нашем обходе в вершину <texbr>p</tex>.:** Пробуем найти увеличивающую цепь из вершины <tex>p</tex>.
: Этот обход, запущенный из вершины <tex>v</tex>, либо найдёт увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина уже не сможет стать насыщенной).==Реализация==
: После того* Граф <tex>G\langle V, как все вершины E \rangle</tex> хранится в матрице смежности <tex>v g[i][j]</tex> размера <tex>n </tex> на <tex>n</tex>*<tex>n = 1 ... n_1|V|</tex> будут просмотрены, текущее паросочетание будет максимальным.
'''bool''' dfs(v: Корректность алгоритма следует из '''int'''): '''if''' (used[v]) '''return''' ''false'' used[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержаv]= ''true'' '''for''' to '''in''' g[v] и теоремы, описанной выше.<br> '''if''' (matching[to] ==Релизация=-1 '''or''' dfs(matching[to])): matching[to] =v '''return''' ''true'' '''return''' ''false''
: Граф <tex>G</tex> хранится списками смежности <tex>g[][]</tex>
: Функция <tex>dfs(v)</tex> - обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>.
: В массиве <tex>mt</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, mt[i])</tex>.
  bool dfsfunction '''main'''(int v) {: if fill(used[v]matching, -1) 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() { ... чтение графа ...n mt.assign fill(k, -1); for (int v = 0; v < n; v++) { used.assign(n, ''false''); dfs(vi); } '''for (int ''' i = 0; i < k; i++)1..n '''if ''' (mtmatching[i] != -1) ... вывод ... } print(i, " ", matching[i])
==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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>O(n_1^2n_2).</tex>
==Ссылки==
:Более точная оценка:* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]:В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2)</tex>, где <tex>n_2</tex> — число вершин второй доли.* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
==Источникиинформации==:*[http://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания]<br>: * Асанов М., Баранский В., Расин В. {{--- }} Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

Навигация