Rambler's Top100





11
4. СЛЕДСТВИЯ ИЗ ТЕОРЕМЫ О МАКСИМАЛЬНОМ
ПОТОКЕ
Определение 1
Путь из
s
в
t
называется увеличивающим поток f, если f<c на пря-
мых дугах и f>0 на обратных дугах этого пути.
Следствие 2
Поток f является максимальным тогда и только тогда, когда нет ни
одного пути, увеличивающего поток f.
Доказательство
Необходимость. Допустим f максимальный поток, докажем, что из
s
в
t
нет ни одного пути, увеличивающего поток f. Допустим противное:
существует путь, увеличивающий поток f. Построим новый поток f’:
пути. дуга обратная если
пути; дуга прямая если
потокщему увеличиваю
пути, тпринадлежи не если
)y,x(,)y,x(f
)y,x(,)y,x(f
;f
)y,x(),y,x(f
)y,x('f
)fmin),fcmin(min(
jii
, где
)fc(
ii
разность между пропускной
способностью и величиной потока для каждой прямой дуги пути, уве-
личивающего поток,
j
f
величина потока каждой обратной дуги пути,
увеличивающего поток. Из доказательства теоремы о максимальном
потоке следует, что f поток мощности
v
, что противоречит макси-
мальности потока f.
Достаточность. Допустим, что не существует ни одного увеличи-
вающего поток f пути, тогда множество X, определенное в доказательст-
ве теоремы о максимальном потоке не может содержать сток t. Поэтому,
как и в доказательстве теоремы о максимальном потоке,
)X,X(
раз-
рез, отделяющий
s
от
t
с пропускной способностью, равной величине
потока f. Значит, f- максимальный поток.
Определение 3
Дуга (x,y) насыщена потоком f, если
)y,x(c)y,x(f
и свободна
от потока, если
0)y,x(f
.