42. Потоки в сетях. Теорема Форда и Фалкерсона (с доказательством). Алгоритм нахождения максимального потока

 

Деятельность  современного общества тесно связана с разного рода сетями — возьмите, к примеру, транспорт, коммуникации, распределение товаров и тому подобное. Поэтому математический анализ таких сетей стал предметом фундаментальной важности.

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех u,v \in V. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Неформальное описание

1.    Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

2.    В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

3.    Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

1.   На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью cmin.

2.   Для каждого ребра на найденном пути увеличиваем поток на cmin, а в противоположном ему - уменьшаем на cmin.

3.   Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

4.    Возвращаемся на шаг 2.

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

Если искать не любой путь, а кратчайший, получится алгоритм Эдмондса-Карпа или алгоритм Диница. Эти алгоритмы сходятся для любых вещественных весов за время O(| V || E | ^2) и O(| V |^ 2 | E |) соответственно.

Формальное описание

Дан граф G(V,E) с пропускной способностью c(u,v) и потоком f(u,v) = 0 для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

§     \ f(u,v) \leqslant c(u,v). Поток из u в v не превосходит пропускной способности.

§     \ f(u,v) = - f(v,u).

§     \ \sum_v f(u,v) = 0 \Longleftrightarrow f_{in}(u) = f_{out}(u) для всех узлов u, кроме s и t. Поток не изменяется при прохождении через узел.

Остаточная сеть Gf(V,Ef) — сеть с пропускной способностью cf(u,v) = c(u,v) − f(u,v) и без потока.

Вход Граф \,G с пропускной способностью \,c, источник \,s и сток \,t
Выход Максимальный поток 
\,f из \,s в \,t

1.    f(u,v) \leftarrow 0 для всех ребер \,(u,v)

2.    Пока есть путь \,p из \,s в \,t в \,G_f, такой что \,c_f(u,v) > 0 для всех ребер (u,v) \in p:

1.   Найти \,c_f(p) = \min\{c_f(u,v) \;|\; (u,v) \in p\}

2.   Для каждого ребра (u,v) \in p

1. f(u,v) \leftarrow f(u,v) + c_f(p)

2. f(v,u) \leftarrow f(v,u) - c_f(p)

Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса-Карпа) или поиском в глубину в Gf(V,Ef).

Сложность

Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено O(E*f), где E — число рёбер в графе, f — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за O(E) и увеличивает поток как минимум на 1.

 

 

Теорема Форда — Фалкерсо́на — теорема о максимальном потоке в графе.

Звучит так: величина максимального потока не превышает величины минимального разреза.

Достаточность: любой поток между вершинами t и s меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин "грузов", перевозимых по всем возможным путям из вершины t в s. Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести "груза" больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна сумме всех пропускных способностей рёбер данного сечения. Утверждение доказано.

Отсюда следует, что любой поток меньше или равен величине минимального сечения, а значит и максимальный поток меньше или равен величине минимального сечения.

На этой теореме основан алгоритм Форда — Фалкерсона поиска максимального потока в графе, он же является доказательством необходимости данной теоремы, т.е. оно является конструктивным.

Другое доказательство (через усиление)

Усилим теорему Форда-Фалкерсона следующим образом. Будем доказывать для сети G(V,E) с потоком f равносильность сразу трёх следующих фактов:

1° Поток f - максимальный

2° Пропускная способность минимального разреза равна величине потока f

3° В графе G нет дополняющего пути


1° → 3°. Предположив обратное, получим противоречие, описанное в информации по дополняющем пути в транспортном графе.

3° → 2°. Очевидно, что величина потока f не превышает пропускной способности минимального разреза (S,T). Пусть c(S,T) > f. Тогда рассмотрим разрез, где во множестве S будут все вершины, кроме t. Тогда его пропускная способность не меньше пропускной способности минимального разреза, что, в свою очередь, больше величины потока f. Значит, существует направление (u,t) из S в T, что f(u,t) < c(u,t). Теперь возьмём все такие u и перенесём их в T. Рассмотрев получившийся разрез, заметим, что его пропускная способность тоже больше величины потока. Снова увеличиваем множество T и делаем так до тех пор, пока в множестве S не останется только вершина s. Она же будет первой вершиной в пути, который мы создаём. Теперь смотрим, какую пару мы выбрали прошлым ходом. Пусть это пара (s,u). Тогда к пути добавляем вершину u. Далее смотрим в паре с какой вершиной была на первом месте вершина u. Пусть это (u,v). Тогда далее к пути добавляем вершину v. Делаем так до тех пор, пока не дойдём до вершины t. Однако по построению этот путь является остаточным, что противоречит предположению.

2° → 1°. Как уже говорилось, очевидно, что величина любого потока не превышает пропускной способности минимального разреза, а величина нашего потока f - равна. Тогда величина потока f не меньше величины любого другого потока в нашей сети, т.е. поток f - максимальный.

Это доказательство хорошо тем, что не использует сложный алгоритм нахождения максимального потока в произвольной транспортной сети.