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

UptoLike

ВУЗ: 

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

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

Рубрика: 

40
символом –. Установить резерв вершины а равным ∞, с тем чтобы она
не ограничивала резерв других вершин. Положить
S = {a}.
(2) Если
S – пустое множество, то поток максимизирован. Если S не явля-
ется пустым, то выбираем любой элемент из
S и удаляем его. Полагаем
этот элемент равным
υ.
(3) Если
ω не помечена, (υ, ω) является ребром и ƒ((υ, ω)) < с((υ, ω)). По-
ложить резерв вершины
ω равным минимуму величины с((υ, ω)) - ƒ((υ,
ω
)) и резерва вершины υ. Установить предшественника вершины ω в υ.
Если
ω ≠ z, добавить ω в S.
(4) Если
ω не помечена, (ω υ,) является ребром и ƒ((υ, ω)) > 0. Положить
резерв вершины
ω равным минимуму из ƒ((υ, ω)) и резерва вершины υ.
Установить предшественника вершины
ω в υ. Если ω во множество S.
(5) Если
z помечена, то, используя функцию предшествования, вернуться
в вершину
а и для каждого ребра цепи добавить резерв вершины z к
потоку каждого правильно ориентированного ребра, и вычесть резерв
z из потока каждого неправильно ориентированного ребра. Вернуться
к шагу 1.
(6) Вернуться к шагу 2.
Требуется еще доказать, что алгоритм действительно определяет макси-
мальный поток, но сначала посмотрим, как он работает.
Пример. Найдем максимальный поток для сети, изображенной на рис. 2.8.
Рис. 2.8
На шаге 1 для каждой вершины устанавливаем предшественника и резерв равными
символу – , для вершины а устанавливаем резерв, равный ∞, и полагаем S = {а}. После чего
получаем сеть, изображенную на рис. 2.9.
Рис. 2.9
b
c
z
d
a
6
3
5
7
2
2
b (-,-)
c (-, -)
z (-, -)
d
(-, -)
a (-,
∞
)
(6, 0)
(3, 0)
(5, 0)
(7, 0)
(2, 0)
(2, 0)

Страницы