Алгоритм поиска максимального потока методом аугментального пути

Эффективный подход к решению задачи о максимальном потоке был разработан Л.Р. Фордом (L.R. Ford) и Д.Р. Фалкерсоном (D.R. Fulkerson) в 1962 г. Это обобщенный ме­тод предусматривает инкрементное увеличения потоков вдоль пути от истока к стоку, который является основой для целого семейства алгоритмов. В классической литературе он известен под названием метода Форда-Фалкерсона (Ford-Fulkerson method); широкое рас­пространение также получил более образный термин, метод аугментального пути (augmenting path method).

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

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

ку вычисления потока в сети: находим другой путь, наращиваем поток вдоль этого пути и продолжаем эту процедуру до тех пор, пока каждый из таких путей, ведущих из исто­ка в сток, не получит, по меньшей мере, одно заполненное ребро (так что больше мы не сможем наращивать потоки подобным способом). В одних случаях такой алгоритм вычис­ляет максимальный поток, в других случаях это ему не удается. На рис. 22.6. показан слу­чай, когда этому алгоритму не удается вычислить максимальный поток.

Чтобы усовершенствовать рассматриваемый алгоритм таким образом, чтобы он все­гда находил максимальный поток, мы рассмотрим более общий способ наращивания по­тока вдоль произвольного пути, ведущего из истока в сток в неориентированном графе, положенном в основу сети. Ребра такого пути относятся либо к категории прямых (forward) ребер, направления которых совпадают с направлением потока (когда мы следуем по пути из истока в сток, мы идем по ребру из его начальной вершины в его конечную вер­шину), либо к категории обратных (backwafd) ребер, которые направлены против пото­ка (при общем направлении из истока в сток, мы идем вдоль ребра из его конечной вер­шины в его начальную вершину). Теперь мы имеем возможность нарастить поток в сети по любому пути за счет увеличения потоков в прямых ребрах и уменьшения потоков в об­ратных ребрах. Величина, на которую поток может быть увеличен, ограничивается мини­мальной неиспользованной пропускной способностью и потоком в обратных ребрах. На рис. 22.12 показан соответствующий пример. В новом потоке, по меньшей мере, одно из прямых ребер, включенных в путь, заполняется, либо одно из обратных ребер, включен­ных в путь, становится пустым.

Описанный выше процесс служит основой классического алгоритма Форда-Фалкер­сона вычисления максимального потока (алгоритм аугментального пути). Сформулируем его следующим образом:

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

РИСУНОК 22.12. НАРАЩИВАНИЕ ПОТОКА ВДОЛЬ ПРОИЗВОЛЬНОГО ПУТИ

Представленная на рисунке последовательность диаграмм служит иллюстрацией наращивания потока в сети вдоль пути, включающего как прямые, так и обратные ребра. Отправляясь от потока, изображенного на левой диаграмме и выполняя операции слева направо, мы сначала наращиваем поток в ребре 0-2, а затем в ребре 2-3 (дополнительные потоки показаны черным цветом). Далее мы уменьшаем поток в ребре 1-3 (показан белым цветом) и отводим извлеченную часть этого потока в ребро 1-4, а затем в 4-5, в результате чего получаем поток, показанный на правой диаграмме.

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

Как ни странно, но этот метод всегда находит максимальный поток независимо от способа выбора путей. Подобно методу отыскания дерева MST, обсуждавшегося в раз­деле 20.1, и методу Беллмана-Форда поиска кратчайшего пути, обсуждавшегося в разде­ле 21.7, это общий алгоритм, который полезен тем, что постулирует правильность всего семейства более специализированных алгоритмов. Мы свободны в выборе любого из этих методов, как бы мы не выбирали путь.

Рисунок 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, обратное ребро ведет в другом направлении. В показанное на этой диаграмме сечение входят четыре прямых ребра и два обратных ребра.