Или приток равен истечению для объединения двух множеств.

Мы можем обойтись и без фиктивных вершин

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

Глава 22, Потоки в сетях

РИСУНОК 22.8. ПРЕДСТАВЛЕНИЕ В ВИДЕ ЦИКЛИЧЕСКИХ ПОТОКОВ

Эта диаграмма показывает, что циркуляция слева разбивается на четыре цикла 1-3-5-4-1, 0-1-3-5-4-2-0, 1-3-5-4-2-1, 3-5-4-3 с весами, соответственно 2, 1, 1 и 3. Каждое ребро каждого цикла появляется в соответствующем столбце, а суммирование весов каждого ребра в каждом цикле, в котором оно появляется (по соответствующей строке), дает его вес в циркуляции.

Если задано множество циклов и величин потоков для каждого цикла, то легко вы­числить соответствующую циркуляцию путем обхода каждого цикла и добавления указан­ной величины потока в каждое ребро. Обратное свойство более интересно: мы можем найти множество циклов (и величину потока для каждого из них), которое эквивалент­но любой заданной циркуляции.

Свойство 22.2. (Теорема декомпозиции потоков). Любая циркуляция может быть пред­ставлена как поток в некотором множестве из максимум Е направленных циклов.

Доказательство: Этот результат устанавливает простой алгоритм. Будем повторять сле­дующий процесс до тех пор, пока имеются ребра, по которым проходят потоки: от­правляясь от произвольного ребра, в котором протекает поток, проследуем вдоль лю­бого ребра, исходящего из вершины назначения первого ребра и в свою очередь содержащего поток, и продолжаем эту процедуру до тех пор, пока не попадем в вер­шину, которую мы уже посетили (был обнаружен цикл). Выполним обратный обход обнаруженного цикла с тем, чтобы найти ребро с минимальным потоком; затем умень­шим потоки в каждом ребре цикла на это значение. Каждая итерация этого процесса уменьшает поток до 0, по меньшей мере, в одном ребре, следовательно, существуют, по меньшей мере, Е циклов. ■

Рисунок 22.9 иллюстрирует процесс, описанный в доказательстве. В случае st-потоков, применение этого свойства к циркуляции, полученной путем добавления ребра из s в t, позволяет сделать вывод о том, что любой st-поток может быть представлен как поток вдоль некоторого множества, состоящего из максимум Е ориентированных путей, каж­дый из которых есть либо путь из s в t, либо цикл.

Следствие. Любая st-сетъ обладает максимальным потоком, подграф которого, индуциро­ванный потоками ненулевой величины, есть ациклический граф.

Доказательство: Циклы, которые не содержат ребра t-s, не меняют величины потока в сети, и в силу этого обстоятельства мы можем присвоить потоку в любом таком цик­ле величину 0, не меняя величины потока в сети. ■

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

РИСУНОК 22.9. ПРОЦЕСС ДЕКОМПОЗИЦИИ ПОТОКОВ ЦИКЛА

Чтобы разложить произвольную циркуляцию на множество циклов, мы многократно выполняем следующий процесс: следуем вдоль некоторого пути до тех пор, пока не встретим какой-либо узел второй раз, затем отыскиваем минимальный вес в обнаруженном цикле, после чего вычитаем минимальный вес из весов каждого ребра обнаруженного цикла и удаляем каждое ребро, вес которого получил значение 0. Например, на первой итерации мы производим обход вдоль пути 0-1-3-5-4-1, на котором обнаруживаем цикл 1-3-5-4-1, далее мы вычитаем 1 из весов всех ребер цикла, по результа­там этого вычитания мы должны удалить из цикла ребро 4-1, так как его вес принимает значение 0. На второй итерации мы удаляем ребра 1-3, 4-2 и 2-1, а на последней итерации удаляем 3-5, 5-4 и 4-3.

Следствие. Любая st-сеть обладает максимальным потоком, который может быть пред­ставлен как поток вдоль множества максимум Е ориентированных путей из s в t

Доказательство: Непосредственно следует из выше сказанного. ■

Все сказанное позволяет получить представление о внутренней структуре потоков, которое будет весьма полезно при разработке и анализе алгоритмов отыскания макси­мальных потоков.

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

Чтобы реализовать алгоритм отыскания максимального потока, мы воспользуемся классом GRAPH из главы 20, организовав указатели на более сложный класс EDGE. Вме­сто одного веса, что делалось в главах 20 и 21, мы используем приватные элементы дан­ных pcanи pflow (а также общедоступные функции-элементы cap () и flow(), которые воз­вращают значения этих элементов данных), соответственно, для пропускной способности и потока. Несмотря на то что сети являются ориентированными графами, рассматривае­мые нами алгоритмы требуют обхода ребер в обоих направлениях, поэтому мы исполь­зуем представление в виде неориентированного графа, которое применялось в главе 20, и функцию-элемент from, которая отличает ребро u-v от ребра v-u.