2.5.2. Алгоритм поиска максимального потока

Рис. 2.13

Ключевым для построения алгоритма решения задачи (2.3) – (2.5) является понятие увеличивающей цепи. Пусть в сети уже имеется какой-либо поток, равный V. Если на какой-либо дуге сетиf_ij<C_ij, то поток на этой дуге может быть увеличен на величину, не превосходящуюC_ij-f_ij. Поэтому поток в сетиVможет быть увеличен, если найдется путь изsвt, для всех дуг которогоf_ij<C_ij. По такому пути может быть пропущено количество единиц потока, равное минимальному из чиселC_ij-f_ijдля всех дуг пути. Это число можно считать пропускной способностью пути. Можно попытаться найти максимальный поток в сети следующим образом: искать путь с наибольшей пропускной способностью и пропускать по нему максимально возможное количество единиц потока, продолжать это, пока такие пути существуют. Однако легко убедиться, что эта процедура не всегда приводит к цели. Например, для графа на рис. 2.13 при первом поиске будет найден путь(s,2,3,t), имеющий пропускную способность 5, и если пропустить по нему 5 единиц потока, то после этого в сети больше не будет путей с положительной пропускной способностью. Между тем максимальный поток в этой сети равен 7, как это видно из рис. 2.13 (числа на дугах – пропускная способность, в скобках – поток).

Поэтому авторами алгоритма (Форд, Фалкерсон) было введено более широкое понятие увеличивающая цепь. Введем в рассмотрение два множества дуг. ПустьI– множество дуг(i,j)сети таких, чтоf_ij<C_ij. На этих дугах поток может быть увеличен наu_ij=C_ij-f_ijединиц, поэтому они называютсяувеличивающими дугами. Далее, обозначимRмножество дуг таких, чтоf_ij>0. На них поток может быть уменьшен наv_ij=f_ijединиц, это –уменьшающие дуги. Очевидно, некоторые дуги могут принадлежать обоим множествам.

Рис 2.14

Цепь, соединяющую узлы sиt, будем называть увеличивающей, если все

ее прямые дуги (ориентированные в направлении от sкt) принадлежат множествуI, а все обратные дуги – множествуR. Вдоль такой цепи может быть проведено увеличение потока на количество единицv, равное минимальному из чиселu_ijдля прямых дуг и чиселv_ijдля обратных. Для этого следует прибавитьvк потокамf_ijна прямых дугах, и вычестьvизf_ijна обратных дугах. Можно убедиться, что при этом условия (2.7)-(2.8) для потока в сети остаются выполненными. В самом деле, для промежуточных вершин цепи возможны четыре случая (рис 2.14). Если обе смежные дуги цепи – прямые (узелi), то заходящий поток увеличивается наv, выходящий – тоже увеличивается наv. Если одна из дуг прямая, а другая – обратная, то либо заходящий (как для узлаj) либо выходящий (узелk) поток увеличивается и уменьшается наv. Если же обе дуги – обратные (узелl), то заходящий поток уменьшается наv, выходящий – тоже уменьшается наv. Во всех случаях разность заходящего и выходящего потоков не меняется и остается равной нулю. Также можно убедиться, что выходящий изsи заходящий вtпоток увеличиваются наv, независимо от того, какого типа дуги являются смежными с этими узлами.

Если в сети проводить увеличение потока не только вдоль путей, но и вдоль увеличивающий цепей, то максимальный поток рано или поздно будет найден. Так, если в сети на рис. 2.13 при нулевых потоках пропустить по пути (s,2,3,t)5 единиц, то после этого больше не будет увеличивающих путей, но будет увеличивающая цепь(s,3,2,t).

Опишем сначала алгоритм поиска максимальной увеличивающей цепи. Он основан на рассмотренном ранее методе пометок. Пустьd(i) - метка узла, в данном случае – пропускная способность найденной увеличивающей цепи в узелi,X– множество вершин. Меткаl(i), как и в алгоритме Дийкстры, вводится, чтобы можно было найти последовательность вершин, образующих увеличивающую цепь.

Шаг 1. Положить d(s)=, d(i)=0 приis,l(i)=0, X=

Шаг 2. Если tX,то СТОП: максимальная увеличивающая цепь найдена.

Шаг 3. Если для всех iX d(i)=0 ,то СТОП: не существует увеличивающей цепи в вершины, не входящие вX. Иначе среди вершинiXнайти вершинуnс максимальной меткой.

Шаг 4. Включить вершину nв множествоX, для всехk Xвыполнить: Если в сети есть дуга(n,k)I(прямая, увеличивающая), то положитьd(k)=max{d(k), min{d(n), C_nk-f_nk}}. Если при этом значениеd(k)изменяется, тоl(k) положить равнымn. Если в сети есть дуга(k,n)R(обратная, уменьшающая), то положитьd(k)=max{d(k),min{d(n), f_kn}}. Если при этом значениеd(k)изменяется, тоl(k) положить равнымn.

Перейти к шагу 2.

Если алгоритм заканчивает работу на шаге 2, то по меткам , как в алгоритме Дийкстры, может быть найдена увеличивающая цепь, поток в сети может быть увеличен по этой цепи на величину, равную метке d(t). Если же остановка происходит на шаге 3, то это означает, что в вершины, включенные вX, есть увеличивающие цепи, а в вершины, не включенные вX, - нет. То есть, для прямых дуг из вершинXв остальные вершиныf_ij=C_ij, а для обратных дугf_ij=0. Значит, множествоXопределяет насыщенный разрез, и максимальный поток найден.

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

Шаг 1. Положить f_ij=0для всехi,j=1,…,N.

Шаг 2. Определить множества дуг IиR. Выполнить алгоритм поиска максимальной увеличивающей цепи. Если она не найдена, то СТОП: множествоXопределяет насыщенный разрез.

Шаг 3. Провести увеличение потока вдоль найденной цепи: добавить d(t)к потокамf_ijна прямых дугах, вычестьd(t)из потоковf_ijна обратных дугах. Перейти к шагу 2.

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

Рис. 2.15

Рис. 2.16 Рис. 2.17

Пример 1. Применим данный алгоритм для поиска максимального потока из вершины 1 в вершину 6 в сети на рис. 2.15. Числа у вершин – метки d(i)после первого поиска увеличивающей цепи. Поток может быть увеличен на 6 единиц, максимальная увеличивающая цепь проходит через вершины (1,2,4,6). Второй поиск приводит к результату на рис. 2.16, поток увеличивается на 5 единиц вдоль цепи (1,3,5,6). Далее, при последующих итерациях алгоритма, поток увеличивается вдоль цепи (1,2,4,3,5,6) на 3 единицы (рис.2.17), вдоль цепи (1,2,3,4,5,6), содержащей обратную дугу, на 1 единицу (рис.2.18). Наконец, при следующем поиске увеличивающей цепи, в множествоXпоследовательно включаются вершины 1,2,3,4, а у вершин 5 и 6 остаются нулевые метки. Это означает, что увеличивающей цепи нет, в сети найден максимальный поток, множествоXопределяет насыщенный разрез (рис. 2.19). Максимальный поток в сети – 15 единиц.

Рис. 2.18 Рис. 2.19

С помощью данного алгоритма можно найти не только максимальный поток в сети, но и минимальный разрез. Это также может быть полезным при решении ряда задач.

Пример 2. Города AиBсоединены между собой сетью автодорог, проходящих еще через несколько населенных пунктов. Для пресечения незаконной торговли администрацией округа решено построить на некоторых дорогах контрольно-пропускные пункты (КПП), так чтобы было невозможно проехать изAвB, минуя их все. Стоимость содержания КПП для каждого участка дорог известна. Где их нужно разместить, чтобы минимизировать суммарную стоимость содержания?

Для решения этой задачи нужно построить сеть, в которой дуги соответствуют различным участкам дорог, найти в ней максимальный поток из AвB, считая стоимости содержания КПП пропускными способностями дуг. Насыщенный разрез определяет множество дорог, на которых следует построить КПП.