Алгоритм Форда-Фалкерсона для поиска максимального паросочетания

Идея алгоритма

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

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

[math]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\} [/math].

Пример графа G.

Соответствующий граф G'.

Изначально текущее паросочетание пусто. На каждом шаге алгоритма будем поддерживать следующий инвариант: в текущее найденное паросочетание входят те и только те ребра, которые направлены из [math]R[/math] в [math]L[/math].

1. Ищем в графе [math]G'[/math] путь из [math]s[/math] в [math]t[/math] поиском в глубину.
2. Если путь найден, перезаписываем текущее паросочетание. Далее инвертируем все рёбра на пути (ребро [math](u, v)[/math] становится ребром [math](v, u)[/math] ) и удаляем [math](s, L)[/math] и [math](R, t)[/math] ребра, покрывающие вершины, принадлежащие текущему паросочетанию.
3. Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.

Корректность алгоритма

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

Т. к. [math]p'[/math] — путь в двудольном графе, начинающийся в [math]L[/math] и заканчивающийся в [math]R[/math], то он нечетной длины. Вершины в нем не повторяются (т.к. это путь в дереве поиска в глубину). Рассмотрим текущее паросочетание. Согласно поддерживаемому инварианту [math](R,L)[/math]-ребра в паросочетании, а [math](L,R)[/math]-ребра — нет. В таком случае ребра пути [math]p'[/math] можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми ребрами текущего паросочетания. Заметим, что путь может начинаться и заканчиваться только в свободной вершине, т. к. из [math]s[/math] ведут ребра только в свободные вершины и только из свободных вершин ведут ребра в [math]t[/math]. Итак, теперь ясно, что [math]p'[/math] — дополняющая цепь для графа [math]G[/math].

Обратно, пусть существует дополняющая цепь в графе [math]G[/math]. В одной из ориентаций она начинается в какой-то свободной вершине [math]u \in L\[/math] и заканчивается в свободной вершине [math]v \in R\[/math], далее будем рассматривать именно эту ориентацию. Ребра поочередно то не лежат, то лежат в паросочетании, значит в нашей ориентации эти ребра поочередно ориентированы то [math](L, R)[/math], то [math](R,L)[/math]. Заметим что эта ориентация совпадает с ориентацией ребер на пути, а значит в нашем ориентированом графе существует путь из свободной вершины [math]u \in L[/math] в свободную вершину [math]v \in R[/math]. Нo каждая свободная вершина из [math]L[/math] связана ребром с [math]s[/math] в графе [math]G'[/math], аналогично каждая свободная вершина из [math]R[/math] связана ребром с [math]t[/math]. Не сложно заметить, что, в таком случае, [math]t[/math] достижим из [math]s[/math], а значит в процессе поиска в глубину будет найден некий [math]s \rightarrow t[/math] путь [math]p[/math] и соответствующий ему [math]p'[/math].

Утверждение доказано.

Оценка производительности

Поиск в глубину запускается от вершины [math]s[/math] не более чем [math]L[/math] раз, т.к. из [math]s[/math] ведет ровно [math]L[/math] ребер, и при каждом запуске одно из них инвертируется. Сам поиск работает за [math]O(E)[/math], каждая инвертация и перезапись паросочетания так же занимает [math]O(E)[/math] времени. Тогда все время алгоритма ограничено [math]O(VE)[/math].

Псевдокод

В массиве [math]px[/math] хранятся вершины [math]y \in R[/math], инцидентные [math]x_i \in L[/math] в текущем паросочетании, для [math]py[/math] аналогично. Максимальное паросочетание — такие ребра [math](x, y)[/math], что [math]x \in L, y \in R, px[x] = y[/math].

Поиск в глубину, одновременно инвертирующий ребра:

bool dfs(x):
    if vis[x]
        return false
    vis[x] = true
    for [math](x, y) \in E[/math]
        if py[y] == -1
            py[y] = x
            px[x] = y
            return true
        else
            if dfs(py[y])
                py[y] = x
                py[x] = y
                return true
    return false

Инициализация и внешний цикл:

px[] = -1
py[] = -1
is_path = true
while is_path
    is_path = false
    vis[] = false
    for [math]x \in L[/math]
        if px[x] == -1
            if dfs(x)
                is_path = true

Ссылки

• Теорема о максимальном паросочетании и дополняющих цепях
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину

Источники информации

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — "Алгоритмы: построение и анализ", 2-е издание, стр. 758 - 761.