Rambler's Top100





10
Докажем, что
поток из
s
в
t
мощности
v
.
Проверим первое условие определения потока.
Если
)y,x(
не лежит на маршруте, то
)y,x(c)y,x(f0
.
Если
)y,x(
прямая дуга маршрута, то
,)y,x('f 0
).y,x(c)y,x(f)y,x(c)y,x(f)y,x(f)y,x(f)y,x('f
1
Если
)y,x(
обратная дуга маршрута, то
),y,x(c)y,x(f)y,x('f
0
2
)y,x(f)y,x(f)y,x(f)y,x(f)y,x('f
.
Значит, для любых
E)y,x(
)y,x(c)y,x(f0
.
Проверим второе условие определения потока.
v)s,V('f)V,s('f
, так как на маршруте из
s
в
t
лежит дуга
одного из двух видов
f'f
f'f
s
s
v)t,V('f)V,t('f
, так как на маршруте из
s
в
t
лежит ду-
га одного из двух видов
f'f
f'f
t
t
t,sx,)x,V('f)V,x('f 0
, так как на маршруте из
s
в
t
лежит
дуга одного из четырех видов
f'f
f'f
f'f
f'f
x
x
f'f
f'f
f'f
f'f
x
x
Таким образом, получили поток
большей мощности, чем
максимальный, т.е. пришли к противоречию, допустив, что
Xt
.
Значит,
Xt
,следовательно
)X,X(
разрез, отделяющий s от t.
Кроме того из определения множества X следует
)X,X()y,x(),y,x(c)y,x(f
и
)X,X()x,y(,)x,y(f 0
, иначе
Xy
. Поэтому
)X,X(c)X,X(f)X,X(f)X,X(fv
.