|
Увеличивающая цепь: AB, BD, DF;
направление дуг совпадает с направлением потока,
? = min(9 – 0, 6 – 0, 10 – 0) = 6.
|
Новые потоки по дугам цепи:
AB: 0+6=6, BD: 0+6 = 6,
DF: 0+6=6:
|
|
|
|
|
Увеличивающая цепь: AB, BE, EF;
направление дуг совпадает с направлением потока,
? = min(9 – 6, 3 – 0, 7 – 0) = 3.
|
Новые потоки по дугам цепи:
AB: 6 + 3 = 9, BE: 0 + 3 = 3,
EF: 0 + 3 = 3:
|
|
|
|
|
Увеличивающая цепь: AC, CE, ED, DF;
направление дуг совпадает с направлением потока,
? = 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 противоположно потоку, направление остальных дуг совпадает с направлением потока,
? = 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;
направление дуг совпадает с направлением потока,
? = min(9 – 8, 6 – 5, 10 – 5) = 1.
|
Новые потоки по дугам цепи:
AB: 8 + 1 = 9, BD: 5 + 1 = 6,
DF: 5 + 1 = 6:
|
|
|
|
|
Увеличивающая цепь: AC, CE, EF;
направление дуг совпадает с направлением потока,
? = 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.
Для построения максимального в сетях с неориентированными дугами поступают следующим образом:
- каждую неориентированную дугу (ребро) сети, не выходящую из источника и не входящую в сток, заменяют парой противоположно направленных дуг с той же пропускной способностью, что и заменяемое ребро;
- каждую неориентированную дугу с началом в источнике заменяют на ориентированную, выходящую из источника;
- каждую неориентированную дугу с концом в стоке заменяют на ориентированную, входящую в сток;
- применяют алгоритм построения максимального потока в сетях, изложенный в разделе 4.1.
Пример сети с неориентированными дугами (BD и EF) и соответствующей ей сети с ориентированными дугами:
— 15 —
|