2. Основная задача о максимальном потоке (от s к t)

Рассмотрим граф с пропускными способностями дуг источником и стоком Множество чисел определенных на дугах , называют потоками в дугах,

если выполняются следующие условия:

и

Уравнение (11.1) является уравнением сохранения потока. Оно утверждает, что поток, втекающий в вершину, равен потоку, вытекающему из вершины, за исключением вершин, являющихся источником и стоком (вершин для которых существуют сетевые вытекания и приток величины соответственно. Соотношения (11.2) указывают просто на то, что пропускные способности ограничены для каждой дуги графа Задача состоит в нахождении такого множества потоков по дугам, чтобы величина

была максимальной. Здесь записаны для потоков из вершины и из соответственно.

Алгоритм расстановки пометок, предложенный Фордом и Фалкерсоном [12] для решения этой задачи, основан на следующей теореме (определение понятия разреза см. в гл. 9).

Теорема 1. (Теорема о максимальном потоке и минимальном разрезе Величина максимального потока из равна величине минимального разреза отделяющего от

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

Минимальный разрез это разрез с наименьшим таким значением.

Доказательство. Здесь дано конструктивное доказательство теоремы о максимальном потоке и минимальном разрезе, и используемый метод непосредственно приводит к алгоритму расстановки пометок, излагаемому ниже.

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

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

Теперь могут возникнуть два случая в зависимости от того, будет ли или

Случай В соответствии с шагом отношение означает следующее: существует такая «неориентированная» цепь, ведущая из вершины в вершину что для каждой дуги используемой цепью в прямом направлении (прямой дуги), Для каждой дуги используемой цепью в обратном направлении, т. е. в направлении от (обратной дуги), (Такая цепь (из дуг), ведущая из будет называться аугменталъной цепью потока.)

Пусть

и

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

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

Случай (т. е. ). В соответствии с шагом Для всех Для всех

Следовательно,

и

т. е. величина потока, а именно

равна величине разреза

Так как в случае (I) поток все время увеличивается по крайней мере на единицу, то при целочисленности всех максимальный поток получим за конечное число шагов — как только возникнет случай Этот поток будет равен тогда величине текущего разреза который, следовательно, должен тогда быть равным минимальному разрезу. Теорема доказана.

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

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