Сведение к максимальному потоку

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

Мы также проведем исследование зависимости между задачей вычисления максималь­ного потока и более сложными задачами с тем, чтобы установить контекст, позволяющий решать эти задачи в дальнейшем. В частности, отметим, что задача о максимальном по­токе представляет собой специальный случай задачи отыскания потока минимальной сто­имости, о которой пойдет речь в разделах 22.5 и 22.6, мы также покажем, как сформу­лировать задачи вычисления максимального потока как задачи линейного программирования, которые мы будем рассматривать в части 8. Задача отыскания пото­ка минимальной стоимости и линейное программирование представляют собой более об­щие модели решения задач, нежели модели максимального потока. И хотя в общем слу­чае мы можем решать задачи о максимальных потоках с применением специальных алгоритмов, описанных в разделах 22.2 и 22.3, с меньшими усилиями, чем с применени­ем алгоритмов, предназначенных для решения более общих задач, очень важно иметь представление о существовании такого рода зависимости между моделями решения задач при переходе к более сложным моделям.

Мы будем употреблять термин стандартная задача о максимальном потоке (standard max/low problem) в отношении версии задачи, которую мы изучали на протяжении после­днего раздела (максимальный поток в st-сетях с ограниченной пропускной способностью ребер). Мы используем этот термин исключительно с целью облегчения ссылок в данном разделе. Итак, мы начнем с того, что покажем, что ограничения, обусловленные стандар­тной задачей о максимальном потоке, по существу не играют важной роли, поскольку несколько других задач о потоках сводятся стандартной задаче или эквивалентны ей. Мы можем рассматривать любую из эквивалентных задач как " стандартную" задачу. Простым примером таких задач, который уже упоминался как вытекающие из свойства 22.1, яв­ляется задача отыскания в сетях циркуляции, позволяющая получить максимальный по­ток в заданном ребре. Далее, рассмотрим другие варианты постановки задачи, в каждом случае отмечая их связь со стандартной задачей.

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

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

Свойство 22.14. Задана о максимальном потоке в сетях общего вида эквивалентна зада­че вычисления максимального потока в st-сетях.

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

ребра, входящие в исходную вершину, идут в u, a все исходящие ребра выходят из и*, в то же время пропускная способность ребра u-u* равна пропус­кной способности исходной вершины. Эта конст­рукция показана на рис. 22.32. Потоки в ребрах типа u*-v при любом максимальном потоке в исход­ной сети должны удовлетворять ограничениям на пропускную способность вершин благодаря нали­чию ребер типа u-u*. ■

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

Ациклические сети. Найти максимальный поток в ациклической сети. Осложняет ли наличие циклов в транспортной сети задачу вычисления максимального потока?

Мы уже сталкивались со многими примерами задач обработки орграфов, которые существенно усложня­ются при наличии в орграфах циклов. Возможно самы­ми известными из них следует считать задачи вычисле­ния кратчайших путей во взвешенных орграфах, когда веса ребер могут принимать отрицательные значения (см. раздел 21.7), которые легко решаются за линейное время, когда циклы отсутствуют, и переходят в класс NP-трудных, если циклы допускаются. Как ни стран­но, задача о максимальном потоке в ациклических се­тях ничуть не проще.

Свойство 22.16. Задача вычисления максимального потока в ациклических сетях эквивалентна стандарт­ной задаче о максимальном потоке.

Доказательство: И снова нам достаточно показать, что стандартная задача сводится к ациклической за­даче. Получив в свое распоряжение сеть с V верши­нами и E ребрами, мы строим сеть с 2V+ 2 верши­нами и Е + 3 V ребрами, которая не только не принадлежит к категории ациклических, но и обла­дает простой структурой.

Пусть и* означает и + V, построим двудольный граф, в котором каждой вершине и исходной сети

РИС. 22.32. УМЕНЬШЕНИЕ ПРОПУСК­НЫХ СПОСОБНОСТЕЙ ВЕРШИН

Чтобы решить задачу вычисления максимального потока в сети, показанной в верхней части рисунка, и чтобы этот поток не превосходил граничного значения пропускной способности, заданной массивом capV_y индексированном именами вершин, построим стан­дартную сеть, которая приводится в нижней части рисунка. Для этого необходимо соединить новую вершину и * (где и * означает v+V) с каждой вершиной и, добавить ребро, пропускная способность которого равна пропускной способности вершины и, и включить ребро и *-v для каждого u-v. Каждая пара и-и * заключена в замкнутую линию. Любой поток в нижней сети напрямую соответствует потоку в верхней сети, которая удовлетворя­ет ограничениям, наложенным на пропускные способности вершин.

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

соответствуют две вершины и и и* и каждому реб­ру u-v исходной сети соответствует ребро u*-v той же пропускной способности. Затем добавим в этот двудольный граф исток s и сток t и для каждой вершины и исходного графа, ребро s-u и ребро u*-t, пропускная способность каждого из них рав­на суммарной ребер, исходящих из вершины и в исходной сети. Наряду с этим, пусть, X есть суммар­ная пропускная способность ребер исходной сети, добавим ребра из и в и* с пропускной способнос­тью X + 1. Полученная конструкция представлена на рис. 22.33.

Чтобы показать, что любой максимальный поток в исходной сети соответствует максимальному пото­ку в преобразованной сети, рассмотрим вместо по­токов сечения. Пусть задан любое st-сечение разме­ра с в исходной сети, покажем, как построить st-сечение размера с + Х в преобразованной сети; кроме того, если задан любое минимальное сечение размера с + X в преобразованной сети, мы пока­жем, как построить st-сечение размера с в исходной сети. Таким образом, если задано минимальное се­чение в преобразованной сети, то соответствующее ему сечение в преобразованной сети также являет­ся минимальным. Более того, наше построение дает поток, величина которого равна пропускной способности минимального сечения, т.е. это макси­мальный поток.

В любом заданном сечении исходной сети, который отделяет исток от стока, пусть S представляет собой множество вершин истока, а Т есть множество вершин стока. Постройте сечение преобразованной сети, помещая вершины из S в некоторое множе­ство, содержащее вершину s, а вершины из Т в не­которое множество, содержащее вершину t, и по­мещая вершины и и и* для всех и на одну и ту же сторону сечения, как показано на рис. 22.33. Для каждой вершины и во множестве связей сечения содержится либо s-u, либо P|u*-t|, a u-v* содержит­ся во множестве связей сечения тогда и только тог­да, когда ребро u-v содержится во множестве свя­зей сечения исходной сети; следовательно, суммарная пропускная способность сечения равна пропускной способности исходной сети плюс X.

При любом заданном минимальном st-сечении пре­образованной сети, пусть S* есть множество вер­шины s, a T* - множество вершины t. Наша цель заключается в том, чтобы построить сечение с той

РИСУНОК 22.33. СВЕДЕНИЕ К АЦИКЛИЧЕСКОЙ СЕТИ

Каждая вершина и в сети, изобра­женная в верхней части рисунка, соответствует двум вершинам и и и* (здесь и* означает и + V) в сети, показанной в нижней части рисунка, а каждое ребро u-v верхней сети соответствует ребру u-v * нижней сети. Кроме того, в нижней сети имеются ребра и-и * без пропускных способностей, источник s с ребрами, ведущими в каждую вершину, не отмеченную звездочкой, и сток t, в который ведет ребро из каждой вершины, помеченной звездочкой. Заштрихованные и незаштрихованные вершины (и ребра, соединяющие заштрихованные вершины с незаштрихованными) иллюстрируют прямую зависимость сечений в обеих сетях (см. рассуж­дения по тексту).