Алгоритм построения максимального потока в сети

1. Если поток в сети не задан,

то считать поток нулевым.

2. Пока в сети есть увеличивающие цепи повторять:

· взять любую увеличивающую цепь,

· вычислить наименьшую разность d между пропускными способностями дуг этой цепи и потоками по этим дугам,

· потоки по дугам, направление которых совпадает с направлением потока, увеличить на d,

· потоки по дугам, направление которых противоположно направлению потока, уменьшить на d,

3. Если в сети нет увеличивающих цепей,

то максимальный поток построен,

Пример 1 (Поток в сети не задан). Построить максимальный поток для заданной транспортной цепи.

Данная сеть:	Сеть с нулевым потоком:

Решение.

1. Поток в сети не задан, считаем его нулевым.

2. Пока в сети есть увеличивающие цепи, повторяем:

Увеличивающая цепь: AB, BD, DF; направление дуг совпадает с направлением потока, d = min(9 – 0, 6 – 0, 10 – 0) = 6.	Новые потоки по дугам цепи: AB: 0+6=6, BD: 0+6 = 6, DF: 0+6=6:

 

Увеличивающая цепь: AB, BE, EF; направление дуг совпадает с направлением потока, d = min(9 – 6, 3 – 0, 7 – 0) = 3.	Новые потоки по дугам цепи: AB: 6 + 3 = 9, BE: 0 + 3 = 3, EF: 0 + 3 = 3:

 

Увеличивающая цепь: AC, CE, ED, DF; направление дуг совпадает с направлением потока, d = min(8 – 0, 4 – 0, 4 – 0, 10 – 6) = 4.	Новые потоки по дугам цепи: AC: 0 + 4 = 4, CE: 0 + 4 = 4, ED: 0 + 4 = 4, DF: 6 +4 = 10:

Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.

Пример 2 (Поток в сети задан). Построить максимальный поток для заданной транспортной цепи.

Сеть с заданным потоком:

Решение.

1. Поток в сети задан.

2. Пока в сети есть увеличивающие цепи, повторяем:

Увеличивающая цепь: AB, BD, DE, EF; направление дуги DE противоположно потоку, направление остальных дуг совпадает с направлением потока, d = min(9 – 6, 6 – 3, 4 – 2, 7 – 4) = 2.	Новые потоки по дугам цепи: AB: 6 + 2 = 8, BD: 3 + 2 = 5, DE: 2 – 2 = 0, EF: 4 + 2 = 6:

 

Увеличивающая цепь: AB, BD, DF; направление дуг совпадает с направлением потока, d = min(9 – 8, 6 – 5, 10 – 5) = 1.	Новые потоки по дугам цепи: AB: 8 + 1 = 9, BD: 5 + 1 = 6, DF: 5 + 1 = 6:

 

Увеличивающая цепь: AC, CE, EF; направление дуг совпадает с направлением потока, d = min(8 – 3, 4 – 3, 7 – 6) = 1.	Новые потоки по дугам цепи: AC: 3+ 1 = 4, CE 3+ 1 = 4, EF: 6 + 1 = 7:

Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.

Примечание. Обратите внимание на то, что сети в примерах 1 и 2 и максимальные потоки по ним совпадают, а потоки по некоторым дугам различаются, например, в примере 1 поток по дуге DF равен 10, а в примере 2 по этой же дуге равен 6.