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>:: (Случай, когда <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>to</tex> ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра <tex>(v, to)</tex>.
:** Включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины <tex>v</tex>.
:* Иначе, если уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра <tex>(v, t_0to), (t_0to, p)</tex>. Для этого просто перейдем в нашем обходе в вершину <tex>p</tex>.
:** Пробуем найти увеличивающую цепь из вершины <tex>p</tex>.
:** Если цепь существует, то удаляем из паросочетания ребро <tex>(p, to)</tex>, а вместо него добавляем <tex>(p, v)</tex>
: Этот обход, запущенный из вершины <tex>v</tex>, либо найдёт увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина уже не сможет стать насыщенной).
:Более точная оценка:
:В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1n_1m)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2)</tex>, где <tex>n_2</tex> — число вершин второй доли.
==Источники==
