Часть 5. Алгоритмы на графах. В формулировке задачи о минимальном сечении нет упоминания о потоках, и может показаться, что эти определения не находятся в русле наших обсуждений алгоритма

В формулировке задачи о минимальном сечении нет упоминания о потоках, и может показаться, что эти определения не находятся в русле наших обсуждений алгоритма вы­числения аугментальных путей. На первый взгляд, вычисление минимального сечения (множества ребер) кажется более легким занятием, чем вычисление максимального пути (назначение весов всем ребрам). Ничего подобного, ключевым фактом этой главы явля­ется то, что задачи о максимальном потоке и задачи о минимальном сечении имеют тес­ную внутреннюю связь. Сам по себе метод построения аугментальных путей в сочетании с двумя фактами, касающимися потоков и сечений, служит тому доказательством.

Свойство 22.3. Для любого st-потока поток через каждый st-сечение равен величине это­го потока.

Доказательство: Это свойство является прямым следствием обобщения свойства 22.1, которое мы обсуждали в рамках соответствующего доказательства (см. рис. 22.7). До­бавим ребро t-s, поток в котором равен такой величине, при которой приток равен истечению для любого множества вершин. Далее, для любого st-сечения, для которо­го C_s есть набор вершин, содержащий вершину s, а C₁ есть набор вершин, содержа­щий вершину t, приток в С_s есть приток в вершину s (величина потока) плюс сумма потоков в обратных ребрах, пересекающих сечение; истечение из C_s равно сумме по­токов в прямых ребрах, проходящих через сечение. Равенство этих двух количествен­ных величин дает искомый результат. ■

Свойство 22.4. Величина st-потока не может превышать пропускной способности никакого st-сечения.

Доказательство: Вполне понятно, что поперечный поток через сечение не может пре­взойти пропускную способность этого сечения, так что результат непосредственно сле­дует из свойства 22.3. ■

РИСУНОК 22.15. ВСЕ ST-СЕЧЕНИЯ

В рассматриваемом списке для сети, изображенной слева, представлены все st-сечения, вершины множества, содержащего вершину s, вершины множества, содержащего вершину t, прямые ребра, обратные ребра и пропускная способность (сумма пропускных способностей прямых ребер). Для любого потока поток через все сечения (потоки в прямых ребрах минус потоки в обратных ребрах) один и тот же. Например, что касается потока в сети слева, то поток через сечение, разделяющее вершины 013 и 2 4 5 есть 2 + 1+2 (поток, соответственно, в ребрах 0-2, 1-4 и 3-5) минус 1 (поток в ребре 2-3) или 4. Эти подсчеты дают в результате значение 4 для каждого второго сечения в сети, а поток принимает максимальное значение, поскольку его величина равна пропускной способности минималь­ного сечения (см. свойство 22.5). В этой рассматриваемой сети имеются два минимальных сечения.