Изменения

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

<tex>V' = V \cup \{s, t\}</tex>(т.е. добавим новый исток <tex>s</tex> и сток <tex>t</tex>);

Обазначим доли исходного графа как <tex>L</tex> и <tex>R</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>G</tex>.]] |[[Файл:GrafG2.png|thumb|200px|Соответствующий граф <tex>G'</tex>.]] |} Изначально текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в текущее найденное паросочетание входят те и только те ребра, которые направлены из <tex>R</tex>в <tex>L</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> ребра, покрывающие вершины, принадлежащие текущему паросочетанию.# Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.

2) Обозначим как <tex>p'</tex> путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> без первого и последнего ребра. Пусть онявляется дополняющей цепью для исходного графа <tex>G</tex>, и пусть также существование дополняющей цепи в графе <tex>G</tex> приводит к существованию пути <tex>p'</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы]]: если мы на каком-то шаге можем найти новый путь, т.е дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найденнайти мы уже не можем, инвертируем все ребра на путизначит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать что сделанное предположение действительно верно.

3) Если Т. к. <tex>p'</tex> — путь в двудольном графе, начинающийся в <tex>L</tex> и заканчивающийся в <tex>R</tex>, то он нечетной длины. Вершины в нем не был найден, значит повторяются (т.к. это путь в дереве поиска в глубину). Рассмотрим текущее паросочетание является максимальным . Согласно поддерживаемому инварианту <tex>(R,L)</tex>-ребра в паросочетании, а <tex>(L,R)</tex>-ребра {{---}} нет. В таком случае ребра пути <tex>p'</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми ребрами текущего паросочетания. Заметим, что путь может начинаться и алгоритм завершает работузаканчиваться только в свободной вершине, т. Иначе переходим к пункту 1). из <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>L. Не сложно заметить, что, в таком случае, <tex>t</tex> достижим из <tex>s</tex>, а значит в процессе поиска в глубину будет найден некий <tex>s \rightarrow t</tex> путь <tex>p</tex> и соответствующий ему <tex>p'</tex>.

Очевидно==Оценка производительности== Поиск в глубину запускается от вершины <tex>s</tex> не более чем <tex>L</tex> раз, что путь т.к. из <tex>s</tex> в ведет ровно <tex>L</tex> ребер, и при каждом запуске одно из них инвертируется. Сам поиск работает за <tex>tO(E)</tex> является дополняющей цепью для исходного графа , каждая инвертация и перезапись паросочетания так же занимает <tex>GO(E)</tex>времени. Тогда корректность все время алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]]ограничено <tex>O(VE)</tex>.

bool * <tex>px[]</tex> {{---}} массив вершин <tex>y \in R</tex>, инцидентные <tex>x_i \in L</tex> в текущем паросочетании,* <tex>py[]</tex> {{---}} массив вершин <tex>x \in L</tex>, инцидентные <tex>y_i \in R</tex> в текущем паросочетании,* <tex>vis[]</tex> {{---}} массив, где помечаются посещенные вершины.Максимальное паросочетание {{---}} такие ребра <tex>(x, y)</tex>, что <tex>x \in L, y \in R, px[x] = y</tex>. Поиск в глубину, одновременно инвертирующий ребра: '''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) isPath = ''true'' '''while''' isPath isPath = ''false'' fill(vis, ''false'') '''for''' <tex>x \in L</tex> '''if''' px[x] == -1 '''if''' dfs(x) isPath = ''true'' ==См. также==* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] ==Источники информации==* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн {{---}} "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.

px[[Категория:Алгоритмы и структуры данных]] = -1 py[] = -1 '''while''' (changed) changed = false vis[Категория:Задача о паросочетании] = false '''for''' для каждой <tex>x \in L</tex> '''if''' (px[x] == -1) '''if''' dfs(x) changed = true