![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 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 и вершины v работает и в том случае, когда мы заменяем вершину v некоторым множеством Т (которое не пересекается с S). Иллюстрацией этого свойства может служить пример, показанный на рис. 22.7. ■ РИСУНОК 22.7. РАВНОВЕСИЕ ПОТОКОВ Эта диаграмма служит иллюстрацией сохранения равновесия потоков при объединении множеств вершин. Две фигуры меньших размеров соответствуют двум произвольным непересекающимся множествам вершин, а буквы представляют множества ребер: А есть количество потока, втекавшего в множество слева извне относительно множества, изображенного справа, х есть количество потока, втекающего в множество слева из множества справа и так далее. Теперь, если установлено равновесие между двумя этими потоками, должно выполняться равенство А+х=В+у для множества слева и C+y = D+x для множества справа. Суммируя эти два равенства и исключая сумму х +у, мы приходим к заключению, что A + C = B + D,
|