Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 22. Потоки в сетях 381
|
|
Другими словами, сечения представляют собой узкие места сети. В рассматривавшемся выше военном приложении противник, который не способен полностью отрезать вражеские войска от их баз снабжения, должен учитывать, что снабжение вражеских войск будет ограничено максимум пропускной способностью любого заданного сечения. Разумеется, мы можем предполагать, что затраты на построение сечения в этом приложении пропорциональны его пропускной способности, заставляя тем самым наступающую армию искать решение задачи о минимальном потоке. Более того, из этих фактов, в частности, вытекает, что ни один поток не может иметь величины, превосходящей пропускную способность любого минимального сечения.
Свойство 22.5. (Теорема о максимальных потоках и минимальных сечениях). Максимальный поток среди всех st-потоков в сети равен минимальной пропускной способности среди всех st-сечений.
Доказательство: Достаточно найти такой поток и такое сечение, чтобы величина потока была равна пропускной способности этого сечения. Этот поток должен быть максимальным, поскольку величина никакого другого потока не может превысить пропускной способности сечения, а сечение должно быть минимальным, поскольку пропускная способность никакого другого сечения не может быть меньше величины потока, протекающего через этот сечение (свойство 22.4). Алгоритм Форда-Фалкерсона точно определяет такой поток и такое сечение: когда этот алгоритм завершает работу, выделите первое заполненное прямое или опорожненное обратное ребро для каждого пути из вершины s в вершину t графа. Пусть Cs есть множество всех вершин, достижимых из s через неориентированный путь, который не содержит наполненного прямого или порожнего обратного ребра, и пусть Ct есть множество всех остальных вершин. Тогда вершина /должна находиться в С,, так что (Сs, C1) естьst/-сечение, разделяющее множество которого состоит исключительно из заполненных прямых или порожних обратных ребер. Поток через это сечение равен пропускной способности этого сечения (поскольку прямые ребра заполнены, а обратные ребра пусты), равной величине потока сети (свойство 22.3). ■
Это доказательство однозначно устанавливает, что алгоритм Форда-Фалкерсона способен отыскать максимальный поток. Независимо от того, какой метод мы выберем для того, чтобы найти аугментальный путь, а также независимо от того, какой путь мы найдем, он всегда заканчивается определением сечения, поток которого равен его пропускной способности, и в силу этого обстоятельства, равен величине потока сети, который по этой причине должен быть максимальным потоком.
Другое следствие правильности алгоритма Форда-Фалкерсона заключается в том, что для любой транспортной сети с целочисленными пропускными способностями ребер, существует решение задачи определения максимального потока, в котором все потоки также принимают целочисленные значения. Каждый аугментальный путь увеличивает величину потока сети на некоторое положительное целое число (минимальная из неиспользованных пропускных способностей в прямых ребрах и потоки в обратных ребрах, величины которых всегда принимают положительные значения). Этот факт оправдывает наше решение уделить основное внимание целочисленным значениям пропускных способностей и величин потоков. Можно применить максимальные потоки с величинами, выраженными нецелыми числами, даже в тех случаях, когда все пропускные способности суть целые числа (см. упражнение 22.23), однако в этом пока нет необходимости.
Часть 5. Алгоритмы на графах
Это ограничение важно само по себе: обобщения, допускающие пропускные способности и потоки, выраженные вещественными числами, могут привести к неприятным аномальным ситуациям. Например, алгоритм Форда-Фалкерсона может привести к появлению бесконечной последовательности аугментальных путей, которые даже не сходятся к величине максимального потока.
Обобщенный алгоритм Форда-Фалкерсона не дает специального описания какого-либо конкретного метода определения аугментальных путей. Возможно, наиболее перспективное направление дальнейших исследований заключается в использовании обобщенной стратегии поиска на графе, рассмотренной в разделе 18.8. С этой целью мы начнем со следующего определения.
Определение 22.4. Пусть задана транспортная сеть и поток в ней, остаточная сеть (residual network) для потока в транспортной сети содержит те же вершины, что и исходная сеть, и одно или два ребра в остаточной сети приходится на каждое ребро исходной сети, которые определены следующим образом: для каждого ребра v-w в исходной сети пусть f есть поток, с — пропускная способность. Если f положительно, следует включить w-v в остаточную сеть с пропускной способностью f; и если f меньше с, необходимо включить ребро v-w в остаточную сеть с пропускной способностью c-f.
Если ребро v-w порожнее (f равно 0), в остаточной сети существует одно ребро, соответствующее v-w, с пропускной способностью с; если ребро v-w заполнено (f равно с), то в остаточной сети существует единственное ребро с пропускной способностью f, соответствующее ребру v-w; и если v-w ни заполнено, ни пусто, то оба ребра v-w и w-v входят в остаточную сеть с соответствующими им пропускными способностями.
Программа 22.2 определяет класс EDGE, который мы используем для реализации абстракции остаточной сети, с функциями-элементами класса. При такой реализации мы будем работать исключительно с указателями на ребра клиентов. Наши алгоритмы работают с остаточной сетью, однако, по существу, они проверяют пропускные способности и изменения потоков (через указатели на ребра) ребер в клиентских программах. Функции-элементы from и Plotherl позволяют производить обработку ребер с любой ориентацией: функция e.other(v) возвращает конечную точку е, которая не есть v. Функции-элементы capRto и addflowRto(v) реализуют остаточную сеть: если е есть указатель на ребро v-w с пропускной способностью с и потоком f; то е-> capRto(w) есть c-f, a e-> capRto(v) есть f; e-> addflowRto(w, d) добавляет величину d к потоку в этом ребре, а е-> addflowRto(v, d) вычитает величину d из этого потока.
Программа 22, 2. Ребра транспортной сети____________________________________
Чтобы реализовать транспортную сеть, мы используем класс GRAPH неориентированного графа из главы 20, позволяющий манипулировать указателями на ребра, которые реализует этот интерфейс. Ребра ориентированы, тем не менее функции-элементы реализуют абстракцию остаточной сети, которая охватывает оба направления каждого ребра (см. текст).