1632
правки
Изменения
м
В массиве <tex>px</tex> хранятся вершины <tex>y \in R</tex>, инцидентные <tex>x_i \in L</tex> Поиск в текущем паросочетанииглубину, для <tex>py</tex> аналогично.одновременно инвертирующий ребра: '''bool''' dfs(x)''':''' '''if''' vis[x] '''return''' ''false'' vis[x] = ''true''Максимальное паросочетание {{---}} такие ребра '''for''' <tex>(x, y)\in E</tex>, что <tex> '''if''' py[y] == -1 py[y] = x px[x \in L, ] = y '''return''' ''true'' '''else''' '''if''' dfs(py[y]) py[y \in R, ] = x px[x] == y</tex>. '''return''' ''true'' '''return''' ''false''
Поиск в глубину, одновременно инвертирующий ребра:
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
'''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 ==Ссылки==''
rollbackEdits.php mass rollback
==Идея алгоритма==
Пусть дан [[Основные определения теории графов|неориентированный двудольный граф ]] <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как [[Файл:GrafG.png|thumb|200px|right|Пример графа G.]][[Файл:GrafG2.png|thumb|200px|right|Соответствующий граф G'.]]
<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>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.
==Псевдокод==
* <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>.
Инициализация и внешний цикл:
==См. также==
* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
==ЛитератураИсточники информации== Кормен, * Томас Х., ЛейзерсонКормен, Чарльз И., РивестЛейзерсон, Рональд Л.Ривест, Клиффорд Штайн Клиффорд {{---}} "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о паросочетании]]
