Cтраница 1
Пропускная способность разреза, естественно, и не уменьшится. Значит, разрез ( Цх, Иу) можно выбрать так, чтобы вершина х не была стоком множества Их. [1]
Пропускная способность разреза при любом разбиении узлов на указанные подмножества определяет верхнюю границу максимально возможной величины потока в сети. Если пропускная способность разреза равна нулю, то узел 0 в буквальном смысле отделен от узла р 1 и поток из источника в сток оказывается невозможным. Следовательно, если допустимый поток равен пропускной способности любого разреза, то он должен быть оптимальным. [2]
Легко видеть, что величина любого потока не превышает пропускной способности любого разреза, и, следовательно, величина любого максимального потока не превышает пропускной способности любого минимального разреза. Однако сразу не ясно, что два последних числа всегда равны между собой; этот замечательный результат называется теоремой о максимальном потоке и минимальном разрезе. Впервые она была доказана Фордом и Фалкерсоном в 1955 г. Мы дадим здесь два доказательства; первое из них показывает, что эта теорема по существу эквивалентна теореме Менгера, а второе является прямым доказательством. [3]
Далее, как было показано выше, число вершин этой опоры равно пропускной способности разреза. [4]
Неравенство в одну сторону очевидно: для произвольного потока и произвольного разреза поток не превосходит пропускной способности разреза. Никакой поток не в состоянии сделать больше, чем просто насытить все дуги, пересекающие разрез, и их общая пропускная способность является верхней гранью для потока. Более трудная задача, как здесь, так и в теореме двойственности, состоит в доказательстве достижимости равенства. [5]
Мы покажем, что каждой опоре можно сопоставить разрез, пропускная способность которого равна числу вершин опоры, и, обратно, каждому разрезу с конечной пропускной способностью можно сопоставить опору, число вершин которой равно пропускной способности разреза. [6]
Разрезом, отделяющим i и /, называется совокупность дуг ( х, у), направленных от некоторого узла в X к некоторому узлу в X. Пропускная способность разреза равна сумме пропускных способностей его дуг. [7]
Тогда множество орребер ( /, /) е Е, обладающих свойством i e S, / е Т, называется разрезом орграфа G. Пропускной способностью разреза ( S, Т) называется сумма пропускных способностей орребер этого разреза. Следующая теорема широко известна как теорема о максимальном потоке и минимальном разрезе. [8]
Пропускная способность разреза при любом разбиении узлов на указанные подмножества определяет верхнюю границу максимально возможной величины потока в сети. Если пропускная способность разреза равна нулю, то узел 0 в буквальном смысле отделен от узла р 1 и поток из источника в сток оказывается невозможным. Следовательно, если допустимый поток равен пропускной способности любого разреза, то он должен быть оптимальным. [9]
Аналогичная ситуация имеет место для дуг ( х, xh), но пропускная способность изменяется здесь на величину Мц. Очевидно, пропускная способность разреза Rv изменяется на величину fvT ], где fv - целое число. [10]
Совокупность ( Х9Х) всех дуг сети, начало которых принадлежит множеству X, а конец - множеству X, будем называть разрезом сети. Суммарная пропускная способность всех дуг разреза называется пропускной способностью разреза. [11]
Рассмотрим, как изменяются пропускные способности разрезов сети при переходе от tv к TV I. Каждому разрезу можно сопоставить пару ( в, у), где 0 - пропускная способность разреза, a f - целый коэффициент, показывающий, что при увеличении TV на г пропускная способность разреза изменяется на чц. [12]
Приведем конструктивное доказательство этойтеоремы ( см [65]), в процессе которого строится максимальный поток и находится минимальный разрез. Если мы покажем, что всегда существует поток, величина которого равна пропускной способности некоторого разреза, то теорема будет доказана, поскольку максимальный поток не превосходит пропускной способности любого разреза, и в частности, минимального. [13]
Рассмотрим, как изменяются пропускные способности разрезов сети при переходе от tv к TV I. Каждому разрезу можно сопоставить пару ( в, у), где 0 - пропускная способность разреза, a f - целый коэффициент, показывающий, что при увеличении TV на г пропускная способность разреза изменяется на чц. [14]
А дуг орграфа D, которое обладает тем свойством, что любая простая орцепь из v в w проходит через дугу, принадлежащую А. Другими словами, разрезом в сети является не что иное, как шьразделяющее множество соответствующего орграфа D. Пропускной способностью разреза называется сумма пропускных способностей принадлежащих ему дуг. Мы будем рассматривать главным образом такие разрезы, которые обладают наименьшей возможной пропускной способностью, - так называемые минимальные разрезы. На рис. 29.1 примером минимального разреза является множество дуг ( v, z), ( x, z) ( у, z) и ( х, w); пропускная способность этого разреза равна шести. [15]