Рис. 27.6 27.6 Работа процедуры FoRD-FuLKERSON. (a)-(d) Шаги выполнения цикла. Слева изображена остаточная сеть Gf (дополняющий путь р выделен серым), справа показан увеличенный поток. Вначале (а) роль остаточной сети играет исходная сеть G. (е) Остаточная сеть более не содержит дополняющего пути; поток максимален.

Анализ алгоритма Форда-Фалкерсона

Время работы процедуры Ford-Fulkerson зависит от того, как ищется путь р (строка 4). В принципе алгоритм может вообще не остановиться, если значение потока будет расти всё более мелкими шагами, так и не достигнув максимума. Однако если выбирать дополняющий путь при помощи поиска в ширину (раздел 23.2), то алгоритм работает полиномиальное время. Прежде чем доказать это, мы установим простую верхнюю оценку для случая целых пропускных способностей. (Этот случай часто встречается на практике. Случай рациональных пропускных способностей сводится к нему умножением на число.)

Для указанного случая (пропускные способности - целые числа), процедура Ford-Fulkerson выполняется за время 0(E\f*\), где /* - максимальный поток. В самом деле, выполнение строк 1-3 требует времени @(Е). Цикл в строках 4-8 выполняется не более /* раз, так как после каждого выполнения величина потока увеличивается по крайней мере на единицу. Осталось оценить время одного шага, которое зависит от того, как мы храним данные о потоке. Рассмотрим ориентированный граф G = (V,E), в котором

Е = {(и, v)\(u, v) £ Е или (v, и) £ Е},

и будем хранить потоки и пропускные способности рядом с соответствующими рёбрами (рёбра сети G входят и в граф G, так что пропускные способности есть где хранить). Остаточная сеть (для текущего потока) состоит из тех рёбер (и, v) графа G, для которых с(и, v) - f[u, v] ф 0. Поиск дополняющего пути в остаточной сети (в глубину или в ширину - пока это всё равно) займет время О(Е) = О(Е). Поэтому время работы процедуры будет 0(E\f*\).

Из доказанной оценки следует, что при небольшом значении /* и целых пропускных способностях время работы процедуры Ford-Fulkerson невелико. Но при большом /* время работы алгоритма может быть велико даже для простой сети, как показывает пример рис. 27.7. Значение максимального потока в этой сети равно 2,000,000 (если использовать рёбра, идущие слева направо). Если, как показано на рис. 27.7 (а) и 27.7 (Ь), на чётных шагах будет выбираться дополняющий путь s -> v -> и -> t, а на нечетных - s -у и -у v -у t, то потребуется 2, 000, 000 шагов, чтобы найти максимальный поток.

Можно получить лучшую оценку времени работы процедуры

Рис. 27.7 27.7 (а) Сеть, для которой процедура FORD-FULKERSON требует времени 0( Б/*), где /* - максимальный поток величины /* = 2000 000. Выделен дополняющий путь с пропускной способностью 1. (Ь) Полученная остаточная сеть. Выделен дополняющий путь с той же пропускной способностью, (с) Полученная остаточная сеть.

Ford-Fulkerson, если предположить, что в строке 4 используется поиск в ширину. В этом случае путь р будет кратчайшим из дополняющих путей (длину каждого ребра считаем равной единице). Эта реализация метода Форда-Фалкерсона называется алгоритмом Эдмондса-Карпа. Докажем, что время работы алгоритма Эдмондса-Карпа равно 0(VE2).

Обозначим длину кратчайшего пути в Gf между вершинами и и v через Sf (и, v)).

Лемма 27.8

Рассмотрим работу алгоритма Эдмондса-Карпа на сети G = (V, Е) с истоком s и стоком t. Для любой вершины v из V \ {s, t] расстояние Sf(s,v) в остаточной сети между истоком и вершиной v G V \ {s, t} монотонно неубывает на каждом шаге цикла.

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

Предположим противное: пусть после увеличения потока / (вдоль дополняющего пути) расстояние Sf(s,v) от истока s до некоторой вершины v из V \ {s, t} уменьшилось. Обозначив увеличенный поток через /, получаем, что

Sf(s,v) < Sf(s,v).

Среди вершин v с таким свойством выберем ближайшую (в смысле сети Gj) к истоку. В этом случае

из Sf(s,u) < Sf(s,v) следует Sf(s,u) Sf(s,u)(27.7)

для всех и G V \ {s, t}.

Возьмем кратчайший путь р из s в v в сети Gj и рассмотрим вершину и, непосредственно предшествующую вершине v в этом пути (s и -> v).

Согласно следствию 25.2, Sj(s,u) = Sj(s,v) - 1. Следовательно, по предположению (27.7)

Sf(s,u) Sf(s,u).

Может ли ребро (и, v) входить в Ef (это значит, что f[u, v] < с(и, v)). Тогда по лемме 25.3 должно быть

Sf(s,v) Sf(s,u) + 1 Sf(s,u) + 1 = = Sf(s,v),

что противоречит начальному предположению.

Следовательно, (и, v) Ef. Но ребро (и, v) принадлежит Ej, поэтому дополняющий путь р, превративший сеть Gf в сеть Gj, содержал ребро (v, и). Так как путь р был кратчайшим путём из s в t в сети Gf, то любой его подпуть также был кратчайшим (лемма 25.1), поэтому Sf(s, и) = 5f(s,v) + 1. Отсюда следует, что

8f(s,v) = Sf(s,u) - 1 <:5f(s,u)-l = = 5f(s,v) - 2 < < f(s,v),

что противоречит начальному предположению. Теорема 27.9

Алгоритм Эдмондса-Карпа на сети G = (V, Е) выполняется за 0(VE) шагов. Доказательство

В каждом дополняющем пути отметим рёбра минимальной пропускной способности, которые будем называть критическими (critical) (для данного шага). Заметим, что критические рёбра исчезают при переходе к следующей остаточной сети.

Покажем, что для одно и то же ребро может быть критическим не более 0(V) раз. Поскольку все рёбра всех остаточных сетей соответствуют рёбрам графа (возможно, в обратном направлении), их число не превосходит 2Е, так что общее число шагов действительно есть O(EV).

Итак, посмотрим, сколько раз за время работы алгоритма Эдмондса-Карпа ребро (и, v) может быть критическим. Если ребро было критическим, оно исчезает, и может появиться вновь лишь после того, как поток из и в v уменьшится. Это может произойти только если ребро (v, и) войдёт в дополняющий путь. Таким образом, возникает последовательность ситуаций:

(и, v) входит в дополняющий путь (и критическое в нём);

(v, и) входит в дополняющий путь (не обязательно критическое);

(и, v) входит в дополняющий путь (и критическое в нём);

(v, и) входит в дополняющий путь (не обязательно критическое);

и так далее. Покажем, что число таких ситуаций есть 0(V). Для этого проследим, как меняются расстояния от истока до вершин и и v в остаточных сетях. Как мы знаем (лемма 27.8), эти две величины могут только возрастать. При этом то одна, то другая вырывается вперёд на 1 (поскольку они соседствуют в кратчайшем пути, лемма 25.1). Заметим, что при переходе от первой ситуации ко второй расстояние от истока до и увеличится по крайней мере на 2 (оно было меньше расстояния до v, а стало больше). При переходе от второй строки к третьей расстояние от истока до v увеличится по крайней мере на 2 и так далее.