Весам дуг можно дать иную интерпретацию, в результате возникает интересная и важная задача. Пусть в ориентированном взвешенном графе выделены две вершины (b – начальная и e – конечная). Предполагается, что вершина e достижима из b. Содержательный смысл весов дуг это пропускная способность дорог. Нас интересуют перевозки из вершины b в вершину e. Естественным является вопрос: какой максимальный груз можно перевезти из начальной вершины в конечную? В отличие от расстояний вес груза, перевозимого по цепи, не равен сумме весов грузов, перевозимых по отдельным дугам. Поставленную задачу называют задачей о максимальном потоке. Слово «поток» здесь является естественным, поскольку можно говорить о потоке грузов, можно задачу интерпретировать и как анализ потоков жидкости в трубопроводах. Приведем формальное определение. Обозначения Г(v), Г-1(v) имеют тот же смысл, что и в предыдущем параграфе.
ОПРЕДЕЛЕНИЕ 35.Потоком в сетиот вершины b к вершине e называется определенная на дугах графа неотрицательная числовая функция x(u,v), удовлетворяющая условиям:
x(u,v)≤ c(u,v);
при u¹b,e;
.
Первое условие означает, что по каждой дуге можно провезти груза не более ее пропускной способности, второе это недопустимость потери потока в промежуточных пунктах (сколько поступает, столько и отправляется), третье отражает тот факт, что из начальной вершины вывозится столько груза, сколько ввозится в конечную, t - величина потока. Задача состоит в том, чтобы найти поток с максимальной величиной.
С понятием потока тесно связано понятие разреза.
ОПРЕДЕЛЕНИЕ 36.Разрезомв графе Г, разделяющим начальную и конечную вершины, называется семейство дуг, после удаления которых в соответствующем неориентированном графе начальная и конечная вершины принадлежат разным компонентам связности (назовем их b-компонентой и e-компонентой).
Образно говоря, разрез это стена, отделяющая конечную вершину от начальной. Разумеется, при добавлении дуг к разрезу также получаем разрез.
Величиной разреза называется сумма весов дуг в разрезе, ведущих из b-компоненты и e-компоненту. Предыдущее замечание говорит о том, что имеет смысл говорить о минимальном разрезе, разделяющем начальную и конечную вершины, как о разрезе с минимальной величиной.
Теорема 27(Форда-Фалкерсона). При заданных начальной и конечной вершинах сети величина максимального потока равна величине минимального разреза.
Доказательство. Прежде всего, величина любого потока не превосходит величины любого разреза. Действительно, из b в e нельзя перевезти груза больше, чем через стену, отделяющую b от e. Таким образом, если мы найдем поток и разрез с равными величинами, то это непременно максимальный поток и минимальный разрез.
Построение фактически является алгоритмом построения максимального потока и минимального разреза, эффективным при целых весах дуг.
При построении важную роль играет следующая конструкция. Рассмотрим последовательность вершин и дуг, соединяющих b и e, причем направления дуг могут быть разными. Дуги, направленные от b к e, назовем прямыми, в противоположном направлении – обратными. (Отметим, что дуга, которая является прямой в одной цепи, может быть обратной в другой). Такая последовательность называется увеличивающей цепью из b в e, если для прямых дуг x(u,v)<c(u,v), а для обратных x(u,v)>0. Пусть p=min{c(u,v)-x(u,v)} для прямых дуг, q=min{x(u,v)} для обратных дуг цепи, r=min{p,q}>0. Поток из b в e можно увеличить по увеличивающей цепи на величину r, положив x(u,v):=x(u,v)+r на прямых дугах и x(u,v):=x(u,v)-r на обратных. Полученные значения также являются потоком (проверьте это!). После такого преобразования цепь не является увеличивающей, поскольку для некоторой прямой дуги x(u,v)=c(u,v) или (не разделительное) для некоторой обратной – x(u,v)=0.
Построение потока с нужными свойствами заключается в последовательном удалении с помощью описанной конструкции увеличивающих цепей и таким образом в увеличении потока из b в e, пока это возможно. В начале поток принимается нулевым. Поскольку при каждой итерации поток увеличивается как минимум на 1 (веса дуг целые!), а величина потока ограничена сверху (например, суммой весов всех дуг графа), то после конечного числа итераций увеличивающих цепей в графе не будет. Полученный поток увеличить нельзя (если бы это можно было сделать, то соответствующая цепь была бы увеличивающей), т.е. он максимальный.
Разобьем множество вершин V на два класса. В первый (V1) входят такие вершины v, для которых существует увеличивающая цепь из b в v, во второй (V2) – остальные вершины. Оба класса непустые: bÎV1, eÎV2, т.е. это b и e-компоненты. Дуги, направленные из V1 в V2 и наоборот, образуют разрез. При этом если (u,v) дуга, uÎV1,vÎV2, то x=c(u,v). Действительно, в противном случае (т.е. при x(u,v)<c(u,v)), присоединив к увеличивающей цепи из b в u дугу (u,v), получим увеличивающую цепь из b в v, что невозможно по построению. Аналогично, если uÎV2,vÎV1, то x(u,v)=0.
Величина построенного разреза равна сумме весов «прямых» дуг. Докажем, что величина построенного максимального потока равна сумме весов тех же дуг. Каждая единица груза доставляется по какой-нибудь из этих дуг, причем по единственной. Если бы таких дуг было более одной, то эта единица груза доставлялась бы по некоторой дуге, ведущей из V2 в V1, а на этих дугах поток нулевой. Теорема Форда-Фалкерсона доказана.
Идея алгоритма, описанного при доказательстве теоремы, реализуется формированием пометок вершин тем или иным образом. Основной недостаток этого подхода состоит в том, что нет никаких указаний относительно построения увеличивающих цепей, а от их выбора сильно зависит число итераций. Во второй половине 20 века разработано множество более простых алгоритмов построения максимального потока.