147
правок
Изменения
м
:'''Краткое описание алгоритма:'''
:* Возьмём пустое паросочетание;
:* Разобьем граф на две доли;
:* Проходя по всем вершинам первой доли пытаемся найти увеличивающую цепь с началом в текущей вершине;
::* Если удается найти увеличивающую цепь, выполняем чередование, то есть если ребро входило в цепь, то удалим его из паросочетания, а если не входило, то наоборот добавим.
:* Найденное паросочетание и является максимальным.
: После того, как все вершины <tex>v = 1 ... n_1</tex> будут просмотрены, текущее паросочетание будет максимальным.
Нет описания правки
: Допустим в паросочетание внесли изменения вдоль дополняющей цепи <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>G(V, E)</tex>, что граф уже разбит на две долигде <tex>V = V_1 + V_2</tex> и <tex>V_1 \cap V_2 = \varnothing</tex>.:Просматриваем все вершины <tex>v</tex> первой доли графа <tex>v = 1 ... n_1u \in V_1</tex>:
:*Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем;
:*Иначе алгоритм пытается насытить эту вершину, для чего запускается запускаем поиск увеличивающей цепи, начинающейся с этой вершины.
:Рассмотрим поиск увеличивающей цепи обходом в глубину.
:* Изначально Запускаем обход в глубину стоит в текущей ненасыщенной вершине от вершины <tex>v</tex> первой доли.
:* Просматриваем все рёбра из этой вершины, пусть текущее ребро — <tex>(v, to)</tex>.
:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то включаем ребро <tex>(v, to)</tex> в паросочетание и прекращаем поиск из вершины <tex>v</tex>.
: Этот обход, запущенный из вершины <tex>v</tex>, либо найдет увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина уже не сможет стать насыщенной).
: После того, как все вершины <tex>u \in V_1</tex> будут просмотрены, текущее паросочетание будет максимальным.
: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]] и теоремы, описанной выше.<br>
