Алгоритм Форда-Фалкерсона для поиска максимального паросочетания — различия между версиями
(→Корректность алгоритма) |
м (rollbackEdits.php mass rollback) |
||
(не показано 7 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
==Идея алгоритма== | ==Идея алгоритма== | ||
− | Пусть дан неориентированный двудольный граф <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как | + | Пусть дан [[Основные определения теории графов|неориентированный двудольный граф]] <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как |
− | |||
− | |||
<tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом: | <tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом: | ||
Строка 8: | Строка 6: | ||
<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>. | <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>R</tex> в <tex>L</tex>. | ||
− | # Ищем в графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</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. | # Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1. | ||
==Корректность алгоритма== | ==Корректность алгоритма== | ||
− | Обозначим как <tex>p'</tex> путь из <tex>s</tex> в <tex>t</tex> без первого и последнего ребра. Пусть он | + | Обозначим как <tex>p'</tex> путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> без первого и последнего ребра. Пусть он |
− | является дополняющей цепью для исходного графа <tex>G</tex> и | + | является дополняющей цепью для исходного графа <tex>G</tex>, и пусть также существование дополняющей цепи в графе <tex>G</tex> приводит к существованию пути <tex>p'</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы]]: если мы на каком-то шаге можем найти новый путь, т.е дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, значит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать что сделанное предположение действительно верно. |
− | Т.к. <tex>p'</tex> — путь в двудольном графе, начинающийся в <tex>L</tex> и заканчивающийся в <tex>R</tex>, то он нечетной длины. Вершины в нем не повторяются (т.к. это путь в дереве поиска в глубину). Рассмотрим текущее паросочетание. Согласно поддерживаемому инварианту <tex>(R,L)</tex>-ребра в паросочетании, а <tex>(L,R)</tex>-ребра {{---}} нет. В таком случае ребра пути <tex>p'</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми ребрами текущего паросочетания. Заметим, что путь может начинаться и заканчиваться только в свободной вершине, т. к. из <tex>s</tex> ведут ребра только в свободные вершины и только из свободных вершин ведут ребра в <tex>t</tex>. Итак, теперь ясно, что <tex>p'</tex> — дополняющая цепь для графа <tex>G</tex>. | + | Т. к. <tex>p'</tex> — путь в двудольном графе, начинающийся в <tex>L</tex> и заканчивающийся в <tex>R</tex>, то он нечетной длины. Вершины в нем не повторяются (т.к. это путь в дереве поиска в глубину). Рассмотрим текущее паросочетание. Согласно поддерживаемому инварианту <tex>(R,L)</tex>-ребра в паросочетании, а <tex>(L,R)</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>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>t</tex> достижим из <tex>s</tex>, а значит в процессе поиска в глубину будет найден некий <tex>s \rightarrow t</tex> путь <tex>p</tex> и соответствующий ему <tex>p'</tex>. |
Утверждение доказано. | Утверждение доказано. | ||
Строка 30: | Строка 32: | ||
==Псевдокод== | ==Псевдокод== | ||
+ | * <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>. | ||
− | + | Поиск в глубину, одновременно инвертирующий ребра: | |
− | + | '''bool''' dfs(x)''':''' | |
+ | '''if''' vis[x] | ||
+ | '''return''' ''false'' | ||
+ | vis[x] = ''true'' | ||
+ | '''for''' <tex>(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. | |
− | |||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Задача о паросочетании]] | [[Категория:Задача о паросочетании]] |
Текущая версия на 19:12, 4 сентября 2022
Идея алгоритма
Пусть дан неориентированный двудольный граф и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как и . Построим граф следующим образом:
(т.е. добавим новый исток и сток );
.
Изначально текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в текущее найденное паросочетание входят те и только те ребра, которые направлены из
в .- Ищем в графе поиском в глубину. путь из в
- Если путь найден, перезаписываем текущее паросочетание. Далее инвертируем все рёбра на пути (ребро становится ребром ) и удаляем и ребра, покрывающие вершины, принадлежащие текущему паросочетанию.
- Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.
Корректность алгоритма
Обозначим как теоремы: если мы на каком-то шаге можем найти новый путь, т.е дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, значит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать что сделанное предположение действительно верно.
путь из в без первого и последнего ребра. Пусть он является дополняющей цепью для исходного графа , и пусть также существование дополняющей цепи в графе приводит к существованию пути . Тогда изТ. к.
— путь в двудольном графе, начинающийся в и заканчивающийся в , то он нечетной длины. Вершины в нем не повторяются (т.к. это путь в дереве поиска в глубину). Рассмотрим текущее паросочетание. Согласно поддерживаемому инварианту -ребра в паросочетании, а -ребра — нет. В таком случае ребра пути можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми ребрами текущего паросочетания. Заметим, что путь может начинаться и заканчиваться только в свободной вершине, т. к. из ведут ребра только в свободные вершины и только из свободных вершин ведут ребра в . Итак, теперь ясно, что — дополняющая цепь для графа .Обратно, пусть существует дополняющая цепь в графе
. В одной из ориентаций она начинается в какой-то свободной вершине и заканчивается в свободной вершине , далее будем рассматривать именно эту ориентацию. Ребра поочередно то не лежат, то лежат в паросочетании, значит в нашей ориентации эти ребра поочередно ориентированы то , то . Заметим что эта ориентация совпадает с ориентацией ребер на пути, а значит в нашем ориентированом графе существует путь из свободной вершины в свободную вершину . Нo каждая свободная вершина из связана ребром с в графе , аналогично каждая свободная вершина из связана ребром с . Не сложно заметить, что, в таком случае, достижим из , а значит в процессе поиска в глубину будет найден некий путь и соответствующий ему .Утверждение доказано.
Оценка производительности
Поиск в глубину запускается от вершины
не более чем раз, т.к. из ведет ровно ребер, и при каждом запуске одно из них инвертируется. Сам поиск работает за , каждая инвертация и перезапись паросочетания так же занимает времени. Тогда все время алгоритма ограничено .Псевдокод
- — массив вершин , инцидентные в текущем паросочетании,
- — массив вершин , инцидентные в текущем паросочетании,
- — массив, где помечаются посещенные вершины.
Максимальное паросочетание — такие ребра
, что .Поиск в глубину, одновременно инвертирующий ребра:
bool dfs(x):
if vis[x]
return false
vis[x] = true
for
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
if px[x] == -1
if dfs(x)
isPath = true
См. также
Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.