Изменения

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

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

Т.к. <tex>p'</tex> — путь в двудольном графе, начинающийся в <tex>L</tex> и заканчивающийся в <tex>R</tex>, то он нечетной длины, . Вершины в котором вершины нем не повторяются (т.к. этот это путь строится с помощью в дереве поиска в глубину). Рассмотрим текущее паросочетание. Мы записывали в него ребра из Согласно поддерживаемому инварианту <tex>(R,L)</tex> -ребра в паросочетании, а <tex>(L,R)</tex>, но после этого инвертировали их. Значит, -ребра текущего паросочетания сейчас ведут из <tex>R</tex> в <tex>L</tex>{{---}} нет. В таком случае ребра пути <tex>p'</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми (ребрами текущего паросочетания. Заметим, что соответствует текущему паросочетанию)путь может начинаться и заканчиваться только в свободной вершине, т. к. из <tex>s</tex> ведут ребра только в свободные вершины и только из свободных вершин ведут ребра в <tex>t</tex>. Тогда этот путь Итак, теперь ясно, что <tex>p'</tex> — дополняющая цепь для графа <tex>G</tex>, и паросочетание можно перезаписать. Обратно — , пусть существует дополняющая цепь в графе <tex>G</tex> это путь нечетной длины . В одной из ориентаций она начинается в какой-то свободной вершине <tex>u \in L\</tex> и заканчивается в свободной вершине <tex>v \in R\</tex>, далее будем рассматривать именно эту ориентацию. Он начинается Ребра поочередно то не лежат, то лежат в паросочетании, значит в какой-нашей ориентации эти ребра поочередно ориентированы то <tex>(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>t</tex>. Тогда любая дополняющая цепь Не сложно заметить, что, в графе таком случае, <tex>Gt</tex> является частью пути достижим из <tex>s</tex> , а значит в процессе поиска в глубину будет найден некий <tex>s \rightarrow t</tex> в графе путь <tex>G'p</tex>, или, что то же самое, является путем и соответствующий ему <tex>p'</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 '''dfsbool'''dfs(x)''':''' '''if''' vis[x] '''return ''' ''false'' vis[x] = ''true'' '''for''' <tex>xy (x, y) \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''

Инициализация и внешний цикл: '''func''' fordFulkerson()''':''' fill(px[] = , -1) fill(py[] = , -1) is_path isPath = ''true;'' '''while''' (is_path)isPath is_path isPath = ''false'' fill(vis[] = , ''false'') '''for''' <tex>x \in L</tex> '''if''' (px[x] == -1) '''if''' dfs(x) is_path isPath = ''true ==Ссылки==''

==ЛитератураИсточники информации== Кормен, * Томас Х., ЛейзерсонКормен, Чарльз И., РивестЛейзерсон, Рональд Л.Ривест, Клиффорд Штайн Клиффорд {{---}} "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.