Оптимизация: предварительное построение паросочетания

Как и в случае Алгоритма Куна, перед выполнением алгоритма Эдмондса можно каким-нибудь простым алгоритмом построить предварительное паросочетание. Например, таким жадным алгоритмом:

for (int i=0; i<n; ++i)

if (match[i] == -1)

for (size_t j=0; j<g[i].size(); ++j)

if (match[g[i][j]] == -1) {

match[g[i][j]] = i;

match[i] = g[i][j];

break;

}

Такая оптимизация значительно (до нескольких раз) ускорит работу алгоритма на случайных графах.

Случай двудольного графа

В двудольных графах отсутствуют циклы нечётной длины, и, следовательно, код, выполняющий сжатие цветков, никогда не выполнится. Удалив мысленно все части кода, обрабатывающие сжатие цветков, мы получим Алгоритм Куна практически в чистом виде. Таким образом, на двудольных графах алгоритм Эдмондса вырождается в алгоритм Куна и работает за  .

Дальнейшая оптимизация

Во всех вышеописанных операциях с цветками легко угадываются операции с непересекающимися множествами, которые можно выполнять намного эффективнее (см. Система непересекающихся множеств). Если переписать алгоритм с использованием этой структуры, то асимптотика алгоритма понизится до  . Таким образом, для произвольных графов мы получили ту же асимптотическую оценку, что и в случае двудольных графов (алгоритм Куна), но заметно более сложным алгоритмом.

    Метод Форда-Фалкерсона (верхняя оценка на время работы; пример, на котором она достигается)

Теорема:

Если   — некоторый поток в сети   с источником   и стоком  , то следующие утверждения эквивалентны: Поток   максимален В   не существует пути   для некоторого разреза   сети

Доказательство:

Докажем от противного. Предположим, что в   существует какой-нибудь путь  . Тогда рассмотрим  . По лемме о сумме потоков   тоже является потоком в сети  , и причем  , что приводит нас к противоречию, что   максимальный поток. Рассмотрим множество   и  . Разбиение   является разрезом, так как по   в   не существует  . По лемме о потоке через разрез  . Также   известно, что  , так как иначе вершина   должна была бы принадлежать множеству  . Поэтому  . Так как существует разрез, такой что  , то согласно следствию леммы о слабой двойственности потока и разреза  , поэтому   максимален

Идея

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0:   для всех   из  . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.

[Править]Реализация

dfs(u, Cmin) {

if (u = t)

return Cmin

u.vis <- true

for (uv in E)

if (!v.vis) && (uv.f < uv.c)

дельта <- dfs(v, min(Cmin, uv.c - uv.f))

if (дельта > 0) {

uv.f += дельта

uv.backEdge.f -= дельта

return дельта

}

return 0

}