Rambler's Top100





8
ЛЕММА О ПОТОКЕ
Дана сеть
).c,t,s,E,V(G
Разрез
)X,X(
отделяет s от t
)Xt,Xs(
, f любой поток из s в t мощности v, тогда
)X,X(c)X,X(f)X,X(fv
.
Другими словами, мощность любого потока не превосходит пропу-
скной способности никакого разреза, отделяющего
s
от
t
.
Доказательство
Так как
Xt
, по определению потока
v)X,V(f)V,X(f
.
Распишем левую часть этого равенства.
).X,X(f)X,X(f
)X,X(f)X,X(f)X,X(f)X,X(f)X,XX(f)XX,X(f
Отсюда
v)X,X(f)X,X(f
.
Докажем, что
)X,X(c)X,X(f)X,X(f
.
Так как для любой дуги
)b,a(
из разреза
)X,X(
выполняется нера-
венство
)b,a(c)b,a(f
, то
)X,X(c)X,X(f
.
)X,X(c)X,X(f)X,X(f)X,X(f
.
Итак,
)X,X(c)X,X(f)X,X(fv
.