Глава 22. Потоки в сетях. этой вершины, и суммарный поток, вытекающий из той или иной вершины, — истече­нием (outflow) этой вершины

этой вершины, и суммарный поток, вытекающий из той или иной вершины, — истече­нием (outflow) этой вершины. По соглашению мы устанавливаем потоки в ребрах, входя­щих в исток, и потоки в ребрах, исходящих из стока, равными нулю, а при доказатель­стве свойства 22.1 покажем, что истечение истока всегда равно притоку стока, этот поток мы будем называть величиной (value) сети. Имея в своем распоряжении эти определения, нетрудно дать формальное определение нашей главной задачи.

Максимальный поток. Пусть задана st-сеть, найти такой поток, что никакой другой поток из s в t не обладает большей мощностью. Будем называть такой поток максималь­ным потоком (maxflow), а задачу построения такого потока в сети будем называть зада­чей о максимальном потоке. В некоторых приложениях нам достаточно знать только кон­кретную величину максимального потока, но общем случае мы хотим знать структуру потока (величины каждого реберного потока), обеспечивающих получение такой вели­чины.

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

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

Свойство 22.1. Любой st-поток обладает тем свойством, что истечение вершины s равно притоку в вершину t.

Доказательство: (В своих рассуждениях мы будем применять термин st-поток (st-flow), который означает " поток в st-сети".) Добавим в сеть ребро, ведущее из фиктивной вершины в вершину s, с потоком и пропускной способностью, равными истечению вершины s, и ребро, ведущее из вершины t в другую фиктивную вершину, с потоком и пропускной способностью, равными втеканию вершины t. Теперь по индукции мы можем доказать более общее свойство: приток равен истечению для любого множе­ства вершин (фиктивные вершины не учитываются).

По условию локального равновесия это свойство характерно для любой одиночной вершины. Предположим теперь, что это свойство выполняется для заданного набора вершин S и что мы добавили в это множество одиночную вершину v, так что теперь

Часть 5. Алгоритмы на графах

имеем множество S'= S U {v}. При вычислении притока и истечения для S', обратите внимание на то обстоятельство, что каждое ребро, ведущее из вершины v в некоторую вершину множества S, уменьшает истечение (из вершины v) на ту же ве­личину, на какую оно уменьшает приток (в S); каждое ребро, ведущее в вершину v из некоторой вершины множества 5, уменьшает приток (в вер­шину v) на ту же величину, на какую уменьшает истечение (из S); все другие ребра обеспечивают приток или истечение из множества S' тогда и только тогда, когда они делают то же самое для S или для v. Таким образом, приток равен истече­нию для S', а величина потока равна сумме вели­чин потоков S и v, минус сумма потоков в реб­рах, соединяющих v с некоторой вершиной в S (в любом направлении).

Применяя это свойство к множеству всех вер­шин, мы находим, что приток в исток из связан­ной с ней фиктивной вершины (который равен истечению истока) равен истечению стока в свя­занную с ним фиктивную вершину (которое рав­но притоку стока). ■

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

Доказательство: Приведенное выше доказатель­ство для множества S и вершины v работает и в том случае, когда мы заменяем вершину v неко­торым множеством Т (которое не пересекается с S). Иллюстрацией этого свойства может служить пример, показанный на рис. 22.7. ■

РИСУНОК 22.7. РАВНОВЕСИЕ ПОТОКОВ

Эта диаграмма служит иллюстраци­ей сохранения равновесия потоков при объединении множеств вершин. Две фигуры меньших размеров соответ­ствуют двум произвольным непересе­кающимся множествам вершин, а буквы представляют множества ребер: А есть количество потока, втекавшего в множество слева извне относительно множества, изобра­женного справа, х есть количество потока, втекающего в множество слева из множества справа и так далее. Теперь, если установлено равновесие между двумя этими потоками, должно выполняться равенство

А+х=В+у для множества слева и

C+y = D+x

для множества справа. Суммируя эти два равенства и исключая сумму х +у, мы приходим к заключению, что

A + C = B + D,