Изменения

Пусть дан [[Основные определения теории графов|неориентированный двудольный граф ]] <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:

<tex>E' = \{(s, u): u \in L\} \cup \{(u, v): u \in L, v \in R\ , (u, v) \in E\} \cup \{(v, t): v \in R\} </tex> (проведем ребра из .{|align="center" |-valign="center" |[[Файл:GrafG.png|thumb|200px|Пример графа <tex>sG</tex> в каждую вершину .]] |[[Файл:GrafG2.png|thumb|200px|Соответствующий граф <tex>LG'</tex>.]] |}Изначально текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в текущее найденное паросочетание входят те и только те ребра, которые направлены из каждой вершины <tex>R</tex> в <tex>t</tex>, и ориентируем все ребра графа <tex>G'</tex> так, чтобы они шли от <tex>u \in L\</tex> к <tex>v \in R\</tex>). Изначально максимальное паросочетание пусто.# Ищем в графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</tex> [[Обход_в_глубину,_цвета_вершин|поиском в глубину]]. # Если путь найден, перезаписываем текущее паросочетание. Далее инвертируем все рёбра на пути (ребро <tex>(u, v)</tex> становится ребром <tex>(v, u)</tex>). После этого перезаписываем текущее паросочетание так, чтобы в него входили ребра этого пути, ведущие из и удаляем <tex>R(s, L)</tex> в и <tex>L(R, t)</tex>ребра, покрывающие вершины, принадлежащие текущему паросочетанию.

# Путь Обозначим как <tex>p'</tex> путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> без первого и последнего ребра. Пусть онявляется дополняющей цепью для исходного графа <tex>G</tex>, и пусть также существование дополняющей цепи в графе <tex>G</tex> приводит к существованию пути <tex>p'</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|дополняющей цепьютеоремы]] для исходного графа : если мы на каком-то шаге можем найти новый путь, т.е дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, значит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать что сделанное предположение действительно верно. Т. к. <tex>Gp'</tex>. Действительно— путь в двудольном графе, начинающийся в этом пути два конца свободны<tex>L</tex> и заканчивающийся в <tex>R</tex>, то он нечетной длины. Вершины в нем не повторяются (т.к. они не являются ребрами графа это путь в дереве поиска в глубину). Рассмотрим текущее паросочетание. Согласно поддерживаемому инварианту <tex>G(R,L)</tex> и-ребра в паросочетании, значита <tex>(L, не входят в паросочетаниеR)</tex>-ребра {{---}} нет. По построению графа В таком случае ребра пути <tex>Gp'</tex> этот можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми ребрами текущего паросочетания. Заметим, что путь содержит нечетное число ребер (может начинаться и заканчиваться только в свободной вершине, т.к. в из <tex>G's</tex> нет ребер ведут ребра только в свободные вершины и только из свободных вершин ведут ребра в <tex>st</tex> в . Итак, теперь ясно, что <tex>y \in Rp'</tex>, а так же ребер из — дополняющая цепь для графа <tex>x \in LG</tex> . Обратно, пусть существует дополняющая цепь в графе <tex>tG</tex>, то попасть . В одной из истока ориентаций она начинается в сток можно только через какиекакой-либо две вершины то свободной вершине <tex>x u \in L\</tex> и заканчивается в свободной вершине <tex>y v \in R\</tex>, расстояние между которыми далее будем рассматривать именно эту ориентацию. Ребра поочередно то не лежат, то лежат в двудольном графе (паросочетании, значит в ребрах) - нечетная величина). В таком случае нашей ориентации эти ребра пути поочередно ориентированы то <tex>s-t(L, R)</tex> можно пронумеровать так, чтобы нечетные ребра были свободнымито <tex>(R, а четные - покрытымиL)</tex>.# Инвертация Заметим что эта ориентация совпадает с ориентацией ребер не меняет на пути, следовательно, он остается дополняющей цепьюа значит в нашем ориентированом графе существует путь из свободной вершины <tex>u \in L</tex> в свободную вершину <tex>v \in R</tex>.# В найденном пути вершины не повторяются (это свойство поиска Нo каждая свободная вершина из <tex>L</tex> связана ребром с <tex>s</tex> в глубину), тогда множество реберграфе <tex>G'</tex>, ведущих только аналогично каждая свободная вершина из <tex>R</tex> в связана ребром с <tex>Lt</tex> является паросочетанием.# Путь не был найден. Это значитНе сложно заметить, что не существует дополняющей цепи для графа , в таком случае, <tex>t</tex> достижим из <tex>s</tex>, а значит в процессе поиска в глубину будет найден некий <tex>s \rightarrow t</tex> путь <tex>p</tex> и соответствующий ему <tex>Gp'</tex>. Тогда по [[Теорема о максимальном паросочетании и дополняющих цепях|теореме]] текущее паросочетание является максимальным Утверждение доказано.

В массиве <tex>px</tex> хранятся вершины <tex>y \in R</tex>, инцидентные <tex>x_i \in L</tex> в текущем паросочетании, для <tex>py</tex> аналогично.Максимальное паросочетание - такие ребра <tex>(x, y)</tex>, что <tex>x \in L, y \in R, px[x] == y</tex>См. bool '''dfs'''(x) '''if''' vis[x] return false vis[x] также== true '''for''' <tex>xy \in E</tex> '''if''' py* [y] = -1 py[yТеорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях] = x px[x] = y return true '''else''' if dfs(py* [y]) py[yАлгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину] = x px[x] = y return true return false

px[] = -1 py[] = -1 is_path Источники информации= true; '''while''' (is_path) is_path = false vis[] = false '''for''' <tex>x \in L</tex> '''if''' (px[x] == * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн {{---}} "Алгоритмы: построение и анализ", 2-е издание, стр. 758 -1) '''if''' dfs(x) is_path = true761.