Графы и сети. Харитонова Е.В. - 46 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

45
() ()
(
)
(
)
(
)
z, c d е b a
5 8,1 4,7 9,0 6,4 9,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
и поскольку резерв z равен 3, прибавляем 3 к каждому потоку, исключая ребро (d, e). Это
ребро ориентировано неправильно; вычитаем 3 из его потока, получая
() ()
(
)
(
)
(
)
z, c d е b a
8 8,4 4,4 9,3 6,7 9,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
что изображено на рис. 2.18.
Рис. 2.18
Начинаем последний проход. Сначала S = {a}. Удаляем вершину а из множества S,
помечаем вершину b(a, 2) и помещаем b в S. Удаляем вершину b из множества S, помечаем
e(b, 2), c(b, 2) и помещаем вершины с, е во множество S. Удаляем е из S, помечаем d(e, 2), по-
скольку резерв d равен минимуму из потока ребра (d, e) и резерва вершины d. Помещаем d в
S. Затем из S удаляем d, но ни один из оставшихся шагов нельзя выполнить, поэтому возвра-
щаемся к шагу 2. Следующим из S удаляем c, но мы не можем выполнить ни один из остав-
шихся шагов и возвращаемся к шагу 2. Множество S пусто, поэтому алгоритм завершен. Ре-
зультат изображен на рис. 2.19
Рис. 2.19
ТЕОРЕМА 2.3. Алгоритм максимального потока строит максимальный
поток для сети.
ТЕОРЕМА 2.4. Поток ƒ на заданной сети
N является максимальным то-
гда и только тогда, когда существует сечение (
S, T), такое, что
()
(
)
T S,C fal =
υ
.
b (а, 5) c (d, 3)
z (с, 3)
a (-, ∞)
d
(
e
,
5
)
e (b, 5)
(4, 1)
(9, 7) (8, 8)
(4, 4)
(8, 8)
(9, 4)
(7, 7)
(6, 3)
b (а, 2) c (b, 2)
z (-, -)
a (-,
∞
)
d
(d, 2)
e (b, 2)
(4, 1)
(9, 7) (8, 8)
(4, 4)
(8, 8)
(9, 4)
(7, 7)
(6, 3)

Страницы