Rambler's Top100





12
Таким образом, одновременно насыщенная и свободная дуга имеет
пропускную способность, равную нулю.
Следствие 4
Разрез
)X,X(
является минимальным тогда и только тогда, когда
каждый максимальный поток f насыщает все дуги разреза
)X,X(
и ос-
тавляет свободными все дуги, принадлежащие
)X,X(
.
Следствие 5
Пусть
)X,X(
и
)Y,Y(
минимальные разрезы. Тогда
)YX,YX(
,
)YX,YX(
минимальные разрезы.
Доказательство
)Y,Y()X,X()YX,Y(
)YX,X()YX,YX()YX,YX(
).Y,Y()X,X()Y,YX()X,YX()YX,YX(
По следствию 4 любой максимальный поток насыщает все дуги
разрезов
)X,X(
и
)Y,Y(
, а значит, и разреза
)YX,YX(
, и ос-
тавляет свободными все дуги разрезов
)X,X(
и
)Y,Y(
, а значит, и
разреза
)YX,YX(
.