Rambler's Top100





9
3. ТЕОРЕМА О МАКСИМАЛЬНОМ ПОТОКЕ
Теорема 1
Дана сеть
)c,t,s,E,V(G
. Разрез
)X,X(
отделяет
s
от
t
.
Мощность максимального потока совпадает с минимальной пропу-
скной способностью разреза, отделяющего
s
от
t
.
Доказательство
В силу леммы о потоке достаточно показать, что существует по-
ток
f
и разрез
)X,X(
, такие, что величина потока и пропускная спо-
собность разреза равны. Действительно, пусть существует поток
f
мощности
0
v
и разрез с пропускной способностью
0
c
, причѐм
00
cv
. По лемме о потоке для любого разреза, отделяющего
s
от
t
, и
любого потока из
s
в
t
выполняются неравенства
,cv,cv
00
где
c
пропускная способность разреза,
v
величина потока. Отсюда
ccvv
00
. Значит,
0
v
мощность максимального потока,
0
c
ми-
нимальная пропускная способность разреза, отделяющего
s
от
t
.
Возьмем максимальный поток
f
и определим его с помощью раз-
реза
)X,X(
для которого
0)X,X(f),X,X(c)X,X(f
. Определим
множество
X
, пользуясь
f
, следующим образом:
Xs
; если
)y,x(c)y,x(f,Xx
, то
Xy
; если
0)x,y(f,Xx
, то
Xy
.
Покажем, что
Xt
. Допустим, что
Xt
, тогда путь из
s
в
t
tx,...,x,xs
n21
обладает тем свойством, что для всех прямых дуг
выполняются неравенства
)x,x(c)x,x(f
iiii 11
, для обратных
неравенства
0
1
)x,x(f
ii
.
Пусть
)x,x(fmin,)x,x(f)x,x(cmin
iiiiii 12111
,
0
21
),,min(
.
Изменим поток
f
следующим образом: увеличим
f
на по всем
прямым дугам пути из
s
в
t
, уменьшим
f
на по обратным дугам,
получим поток
дуга. обратная если
дуга; прямая если
маршруте; на ллежине если
)y,x(,)y,x(f
)y,x(,)y,x(f
)y,x(),y,x(f
)y,x('f