188
правок
Изменения
Нет описания правки
{|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>(x, y)</tex>, что <tex>x \in L, y \in R, px[x] = y</tex>.
Инициализация и внешний цикл:
'''func''' fordFulkerson()''':''' fill(px[] = , -1) fill(py[] = , -1) is_path isPath = ''true'' '''while''' is_pathisPath is_path isPath = ''false'' fill(vis[] = , ''false'') '''for''' <tex>x \in L</tex> '''if''' px[x] == -1 '''if''' dfs(x) is_path isPath = ''true''
==СсылкиСм. также==
* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
