Основные понятия и определения теории потоков Конечный граф (х,т) без петель называется сетью , если каждой дуге

u отнесено целое число C(u) , называемое пропускной способностью дуги.

Этот граф обладает следующими свойствами :

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

• существует одна и только одна вершина z, в которую входят дуги, но ни одна дуга не выходит. Эта вершина называется выходом или стоком сети.

Пусть - множество дуг, входящих в вершину , а - множество

дуг, выходящих из вершины .

Функция  , определенная на множестве дуг сети и принимающая целочисленные положительные значения, представляет собой поток данной транспортной сети, если  (1),

 -  = 0, , (2)

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

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

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

Из соотношения (2) следует  =  = Ф.

Это число Ф называется суммарным потоком на конечных дугах.

П ример

1.1 2.1

2.2 z

4.3 5.3

Ф = 6.

Представим множество всех вершин сети в виде суммы двух подмножеств Р и , где первое подмножество содержит вход сети , а второе – выход сети z. В этом случае будем говорить , что к сети приложен разрез.

Множество дуг , где , , называется разрезом.

Сумма пропускных способностей дуг разреза называется величиной разреза Г.

Пример. Автомобильные дороги и железнодорожные пути.

В общем случае величина потока на конечных дугах никогда не превышает величину разреза Ф Г.

Теорема о максимальном потоке (теорема Форда-Фалкерсона).

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

Пример.

Условие сохранения потока для промежуточных вершин ( и ) удовлетворяется, Ф = 4. Разрез, состоящий из дуг , имеет пропускную способность Г = 4. В разрез не включена дуга поскольку поток  = 0. Суммарный поток на конечных дугах в данной сети будет максимальным, а пропускная способность разреза минимальной.

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

Перейдем теперь к самой теореме.

Необходимо найти такой разрез , чтобы

 = с ( =С , (3)

 = 0  . (4)

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

Максимальный поток * в сети всегда существует,так как значение дугового потока всегда ограничено и дискретно.

Считая, что поток * задан, определим множество следующим рекуррентным способом :

если и  , то

если и  , то (5)

Проанализируем процедуру, которая задается соотношениями (5).

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

Приведем возможные локальные структуры сети :

Из истока дуги могут только исходить.

 



В соответствии с правилами (5) дуга исключается , и вершина не попадет в множество .

 < c

 < c

 > 0

 = c  < c

Вершина не попадет в множество , а вершина попадет в множество , так как . 

Конечный же участок сети будет иметь вид .

Докажем, что конечная вершина (6).

Допустим , что это не так, тогда из определения множества следует , что существует путь из вершины в вершину , т.е. , (7)

который обладает тем свойством, что для прямых дуг цепи  ,

а для обратных дуг  .

 < c  > 0

  с  < c

Обозначим через минимум разности ( с -  ), взятый по всем дугам этого пути , а через минимум , взятый по всем обратным дугам. Введем величину . (8)

Изменим поток , увеличив его на на всех прямых дугах пути, т.е. ₁= + (9) и уменьшив его на обратных дугах на то же самое значение, т.е. ₁ =  - . (10)

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

Ф₁ = ₁  Ф + . (11)

Но последнее соотношение противоречит тому условию, что поток в сети максимальный . Таким образом , соотношение (6) доказано , а из этого следует, что для разреза выполняются равенства (3),(4) и тем самым теорема о максимальном потоке тоже доказана.

Следствие 1. Поток  является максимальным в том случае, если нет ни одного пути, увеличивающего его.

Следствие 2. Если поток в сети не максимальный , то для его увеличения и определения максимального можно использовать преобразования ( 7 – 11 ).

Следствие 3. Для того чтобы поток сделать максимальным, необходимо насытить дуги разреза .

Дуга насыщена, если  , и свободна от потока, если  .

Дуга, одновременно насыщенная и свободная от потока, имеет пропускную способность, равную нулю.

Следствие 4. Разрез минимален в том и только в том случае, если каждый максимальный поток  насыщает все дуги разреза и оставляет свободными все дуги, принадлежащие .