Cтраница 2
Пропускная способность разреза при любом разбиении узлов на указанные подмножества определяет верхнюю границу максимально возможной величины потока в сети. Если пропускная способность разреза равна нулю, то узел 0 в буквальном смысле отделен от узла р 1 и поток из источника в сток оказывается невозможным. Следовательно, если допустимый поток равен пропускной способности любого разреза, то он должен быть оптимальным. [16]
Ср 1 - в любой узел, принадлежащий подмножеству С0, равен нулю. Поэтому общая величина потока в сети равна сумме потоков по всем дугам, исходящим из подмножества С0 и входящим в подмножество CP I. Всем этим дугам соответствуют потоки, равные их пропускным способностям. Следовательно, общая величина потока в найденном решении равна пропускной способности разреза, и дальнейшее увеличение потока оказывается уже невозможным. [17]