![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм поиска максимального потока методом аугментального пути
Эффективный подход к решению задачи о максимальном потоке был разработан Л.Р. Фордом (L.R. Ford) и Д.Р. Фалкерсоном (D.R. Fulkerson) в 1962 г. Это обобщенный метод предусматривает инкрементное увеличения потоков вдоль пути от истока к стоку, который является основой для целого семейства алгоритмов. В классической литературе он известен под названием метода Форда-Фалкерсона (Ford-Fulkerson method); широкое распространение также получил более образный термин, метод аугментального пути (augmenting path method). Рассмотрим произвольный ориентированный путь (не обязательно простой) из истока в сток в st-сети. Пусть х есть минимальное значение неиспользованной пропускной способности ребер на этом пути. Мы можем повысить величину потока в сети, по меньшей мере, на величину х, увеличив поток во всех ребрах, составляющих указанный путь, на эту величину. Неоднократно повторяя это действие, мы осуществляем первую попыт- Глава 22, Потоки в сетях
Чтобы усовершенствовать рассматриваемый алгоритм таким образом, чтобы он всегда находил максимальный поток, мы рассмотрим более общий способ наращивания потока вдоль произвольного пути, ведущего из истока в сток в неориентированном графе, положенном в основу сети. Ребра такого пути относятся либо к категории прямых (forward) ребер, направления которых совпадают с направлением потока (когда мы следуем по пути из истока в сток, мы идем по ребру из его начальной вершины в его конечную вершину), либо к категории обратных (backwafd) ребер, которые направлены против потока (при общем направлении из истока в сток, мы идем вдоль ребра из его конечной вершины в его начальную вершину). Теперь мы имеем возможность нарастить поток в сети по любому пути за счет увеличения потоков в прямых ребрах и уменьшения потоков в обратных ребрах. Величина, на которую поток может быть увеличен, ограничивается минимальной неиспользованной пропускной способностью и потоком в обратных ребрах. На рис. 22.12 показан соответствующий пример. В новом потоке, по меньшей мере, одно из прямых ребер, включенных в путь, заполняется, либо одно из обратных ребер, включенных в путь, становится пустым. Описанный выше процесс служит основой классического алгоритма Форда-Фалкерсона вычисления максимального потока (алгоритм аугментального пути). Сформулируем его следующим образом: Начните выполнение алгоритма в любом месте сети. Наращивайте поток вдоль произвольного пути из истока в сток, содержащего незаполненные ребра или пустые обратные ребра, продолжая этот процедуру до тех пор, пока не останется в сети ни одного такого пути. РИСУНОК 22.12. НАРАЩИВАНИЕ ПОТОКА ВДОЛЬ ПРОИЗВОЛЬНОГО ПУТИ Представленная на рисунке последовательность диаграмм служит иллюстрацией наращивания потока в сети вдоль пути, включающего как прямые, так и обратные ребра. Отправляясь от потока, изображенного на левой диаграмме и выполняя операции слева направо, мы сначала наращиваем поток в ребре 0-2, а затем в ребре 2-3 (дополнительные потоки показаны черным цветом). Далее мы уменьшаем поток в ребре 1-3 (показан белым цветом) и отводим извлеченную часть этого потока в ребро 1-4, а затем в 4-5, в результате чего получаем поток, показанный на правой диаграмме. Часть 5. Алгоритмы на графах
Рисунок 22.13 служит иллюстрацией нескольких различных последовательностей аугментальных путей, каждый из которых позволяет найти максимальный поток в сети, предложенной в качестве примера. Далее в этом разделе мы рассмотрим несколько алгоритмов, которые вычисляют последовательности аугментальных путей; каждый из которых приводит к нахождению максимального пути. Эти алгоритмы различаются по числу аугментальных путей, которые они вычисляют, по длине вычисляемых путей, однако все они реализуют алгоритм Форда-Фалкерсона и находят максимальный поток. Чтобы показать, что любой поток, вычисленный с помощью любой реализации алгоритма Форда-Фалкерсона, и в самом деле имеет максимальную величину, мы покажем, что этот факт эквивалентен ключевому условию, известному как теорема о максимальных потоках и минимальных сечениях (maxflow-mincut theorem). Понимание этой теоремы представляет собой очень важный шаг к пониманию алгоритмов на транспортной сети. Как следует из названия, теорема зиждется на непосредственной зависимости между потока-
РИСУНОК 22.13. ПОСЛЕДОВАТЕЛЬНОСТИ АУГМЕНТАЛЬНЫХ ПУТЕЙ В трех представленных на рисунке примерах мы производим наращивание потока вдоль различных последовательностей аугментальных путей до тех пор, пока станет невозможно найти новые аугментальные пути. Поток, который удается получить в каждом случае, есть максимальный поток. Классическая теорема из теории сетевых потоков утверждает, что мы получаем максимальный поток в любой сети, независимо от того, какую последовательность путей мы используем (см. свойство 22.5). Глава 22. Потоки в сетях
ми и сечениями в сетях, поэтому мы начнем с определения терминов, имеющих отношение к сечениям. Напомним, что в соответствии с определением, данным в разделе 20.1, сечение (cut) графа есть разбиение множества вершин графа на два непересекающихся подмножества, а пересекающее ребро (crossing edge) есть ребро, соединяющее вершину некоторую одного подмножества с вершиной другого подмножества. Применительно к транспортным сетям мы уточним эти определения следующим образом (см. рис. 22.14). Определение 22.3. st-сечение есть сечение, которое помещает вершину s в одно из своих множества, а вершину t — в другое множество. Каждое пересекающее ребро, соответствующее st- сечению, есть либо s/-pe6po, ведущее из вершины, которая принадлежит множеству, содержащему вершину s, в вершину, входящую во множество, содержащую вершину t, либо ts-ребро, которое ведет в обратном направлении. Иногда мы называем множество пересекающих ребер разделяющим множеством (cut set). Пропускная способность st -сечения в транспортной сети есть сумма пропускных способностей ребер этого st-сечения, а поток через st -сечение есть разность между суммой потоков в этих st-pe6pax и суммой потоков в ts-ребрах этого сечения. Удаление разделяющего множества приводит к делению связного графа на две связных компоненты, при этом отсутствуют пути, соединяющие какую-либо РИСУНОК 22.14. ТЕРМИНОЛОГИЯ, ИСПОЛЬЗУЕМАЯ ПРИ ОПИСАНИИ st-СЕЧЕНИЯ В рассматриваемой st-cemu имеется один исток s и один сток t. st-сечение есть разбиение вершин на множество, содержащее вершину s (белые кружки), и множество, содержащее вершину t (черные кружки). Ребра, связывающие вершины одного множества с вершинами другого множества (выделенные серым цветом), представляют собой разделяющее множество. Прямое ребро ведет из вершины множества, содержащего s, в вершину множества, содержащего t, обратное ребро ведет в другом направлении. В показанное на этой диаграмме сечение входят четыре прямых ребра и два обратных ребра.
|