![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сведение к максимальному потоку
В этом разделе мы рассмотрим некоторое число задач, решение которых сводится к решению задаче вычислении максимального потока с тем, чтобы показать, что алгоритмы, которые мы изучали в разделах 22.2 и 22.3, важны в более широком контексте. Мы можем снимать различные ограничения на задачи обработки сетей и графов, и, в конце концов, мы сможем решать задачи, которые выходят за рамки сетевых. В этом разделе будут рассмотрены примеры таких видов использования — определение максимального потока как общая модель решения задачи. Мы также проведем исследование зависимости между задачей вычисления максимального потока и более сложными задачами с тем, чтобы установить контекст, позволяющий решать эти задачи в дальнейшем. В частности, отметим, что задача о максимальном потоке представляет собой специальный случай задачи отыскания потока минимальной стоимости, о которой пойдет речь в разделах 22.5 и 22.6, мы также покажем, как сформулировать задачи вычисления максимального потока как задачи линейного программирования, которые мы будем рассматривать в части 8. Задача отыскания потока минимальной стоимости и линейное программирование представляют собой более общие модели решения задач, нежели модели максимального потока. И хотя в общем случае мы можем решать задачи о максимальных потоках с применением специальных алгоритмов, описанных в разделах 22.2 и 22.3, с меньшими усилиями, чем с применением алгоритмов, предназначенных для решения более общих задач, очень важно иметь представление о существовании такого рода зависимости между моделями решения задач при переходе к более сложным моделям. Мы будем употреблять термин стандартная задача о максимальном потоке (standard max/low problem) в отношении версии задачи, которую мы изучали на протяжении последнего раздела (максимальный поток в st-сетях с ограниченной пропускной способностью ребер). Мы используем этот термин исключительно с целью облегчения ссылок в данном разделе. Итак, мы начнем с того, что покажем, что ограничения, обусловленные стандартной задачей о максимальном потоке, по существу не играют важной роли, поскольку несколько других задач о потоках сводятся стандартной задаче или эквивалентны ей. Мы можем рассматривать любую из эквивалентных задач как " стандартную" задачу. Простым примером таких задач, который уже упоминался как вытекающие из свойства 22.1, является задача отыскания в сетях циркуляции, позволяющая получить максимальный поток в заданном ребре. Далее, рассмотрим другие варианты постановки задачи, в каждом случае отмечая их связь со стандартной задачей. Максимальный поток в сетях общего вида. Найти поток в сети, которая максимизирует суммарное истечение из ее источников (и, следовательно, приток в ее стоки). По соглашению, определяем поток как нулевой в сети, в которой нет истоков либо нет стоков. Часть 5. Алгоритмы на графах
Доказательство: Ясно, что алгоритм вычисления максимального потока в сетях общего вида будет работать на st-сетях, так что нам нужно установить, что задача общего вида сводится к задаче об st-сетях. Чтобы доказать это, найдем сначала истоки и стоки (с использованием, например, метода, который мы применяли для инициализации очереди в программе 19.8), и установим 0, если нет ни того, на другого. Далее, добавим фиктивную вершину-исток s и ребра, ведущие из s во все истоки сети (при этом устанавливаем пропускную способность такого ребра равной истечению вершины назначения этого ребра), а также фиктивное вершину-сток t и ребра, идущие из каждого стока сети в t (при этом устанавливаем Пропускную способность такого ребра равной истечению начальной вершины назначения этого ребра). Рисунок 22.31 может послужить иллюстрацией такого сведения. Любой максимальный поток в st-сетях непосредственно соответствует максимальном потоку в исходной сети. ■ Ограничения, накладываемые на пропускную способность вершин. Пусть задана некоторая транспортная сеть, необходимо вычислить максимальный поток, удовлетворяющий ограничению, в соответствии с которым поток через каждую вершину не должен превышать некоторой фиксированной пропускные способности. Свойства 22.15. Задача вычисления максимального потока в транспортной сети с ограничениями на пропускную способность вершин эквивалентна стандартной задаче о максимальном потоке. Доказательство: И снова мы можем воспользоваться любым алгоритмом, который решает задачу об ограничениях на пропускную способность, для решения стандартной задачи (установив ограничения на пропускную способность в каждой вершине, согласно которому она больше, чем ее приток или ее истечение). В условиях заданного потока в сети с ограничениями по пропускной способности постройте стандартную транспортную сеть с двумя вершинами и и и*, соответствующие каждой исходной вершине и, при этом все РИСУНОК 22.31. СВЕДЕНИЕ ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ В СЕТИ СО МНОГИМИ ИСТОКАМИ И СТОКАМИ К СТАНДАРТНАЯ ЗАДАЧЕ В сети, изображенной в верхней части рисунка, имеются три истока (вершины 1, 2 и 3) и два стока (вершины 5 и 6). Чтобы найти поток, который обеспечивает максимальное истечение из истоков и максимальный приток в стоках, мы вычисляем максимальный поток в st-cemu, представленной в нижней части рисунка. Эта сеть есть копия исходной сети, в которую добавлены исток 7 и сток 8. В каждый исток исходной сети из вершины 7 проводим ребро, пропускная способность которого равна суммарной пропускной способности ребер, исходящих из соответствующего истока, и ребра, ведущие из каждого стока исходной сети в вершину 8, пропускная способность которых равна суммарной пропускной способности ребер, входящих в стоки исходной сети. Глава 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. УМЕНЬШЕНИЕ ПРОПУСКНЫХ СПОСОБНОСТЕЙ ВЕРШИН Чтобы решить задачу вычисления максимального потока в сети, показанной в верхней части рисунка, и чтобы этот поток не превосходил граничного значения пропускной способности, заданной массивом capVy индексированном именами вершин, построим стандартную сеть, которая приводится в нижней части рисунка. Для этого необходимо соединить новую вершину и * (где и * означает v+V) с каждой вершиной и, добавить ребро, пропускная способность которого равна пропускной способности вершины и, и включить ребро и *-v для каждого u-v. Каждая пара и-и * заключена в замкнутую линию. Любой поток в нижней сети напрямую соответствует потоку в верхней сети, которая удовлетворяет ограничениям, наложенным на пропускные способности вершин. Часть 5. Алгоритмы на графах
Чтобы показать, что любой максимальный поток в исходной сети соответствует максимальному потоку в преобразованной сети, рассмотрим вместо потоков сечения. Пусть задан любое 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, в который ведет ребро из каждой вершины, помеченной звездочкой. Заштрихованные и незаштрихованные вершины (и ребра, соединяющие заштрихованные вершины с незаштрихованными) иллюстрируют прямую зависимость сечений в обеих сетях (см. рассуждения по тексту).
|