147
правок
Изменения
Нет описания правки
: Пусть <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><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>v</tex> первой доли.
:* Просматриваем все рёбра из этой вершины, пусть текущее ребро — <tex>(v, t_0to)</tex>.:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра <tex>(v, t_0to)</tex>.
:** Включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины <tex>v</tex>.
:** Иначе, — если уже насыщена каким-то ребром <tex>(p, t_0to)</tex>и не посещена, то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра <tex>(v, t_0), (t_0, p)</tex>. Для этого просто перейдём перейдем в нашем обходе в вершину <tex>p</tex>.:*** Пробуем найти увеличивающую цепь из вершины <tex>p</tex>.
: Этот обход, запущенный из вершины <tex>v</tex>, либо найдёт увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина уже не сможет стать насыщенной).
: После того, как все вершины <tex>v = 1 ... n_1</tex> будут просмотрены, текущее паросочетание будет максимальным.
: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]] и теоремы, описанной выше.<br>
==Релизация==
==Время работы==
:Итак, алгоритм Куна можно представить как серию из |<tex>Ln_1</tex>| запусков обхода в глубину на всём графе.:Следовательно, всего этот алгоритм исполняется за время <tex>O(V Enm)</tex>, где <tex>m</tex> - количество ребер, что в худшем случае есть <tex>O(Vn^3)</tex>. :Более точная оценка::В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2)</tex>, (где <tex>n_2</tex> — число вершин второй доли).
==Источники==
