Метод построения максимального потока в сети

Рассмотрим метод на примере (рис.12). Пусть дана сеть G=(V, E), уз­лом-источником является вершина 1, узлом-стоком — вершина 6. Построим максимальный поток (F) между этими вершина­ми. Начальное значение F нулевое. Очевидно, что структурой данных для описания F является матрица того же типа, что и матрица С, в которой определены пропускные способности дуг.

рис.12

Первая итерация (см. рис.13). Присвоим вершине 1 метку [1, @].

 

рис.13

Шаг 1. Рассмотрим дуги, началом которых является верши­на 1 — дуги (1, 2) и (1, 3). Вершины 2 и 3 не помечены, поэтому присваиваем им метки, для 2-й — [1, 2] и 3-й — [1, 6]. Что пред­ставляют из себя мет­ки? Первая цифра — номер вершины, из которой идет поток, вторая цифра – численное значение потока, который можно передать по этой дуге.

Шаг 2. Выберем помеченную, но непросмотренную вершину. Первой в соот­ветствующей структуре данных записана вершина 2. Рассмотрим дуги, для которых она является началом — дуги (2, 4) и (2, 5). Вершины 4 и 5 не помечены. Присвоим им мет­ки — [2, 2] и [2, 2]. Итак, на втором шаге вершина 2 просмотре­на, вершины 3, 4, 5 помечены, но не просмотрены, остальные вершины не помечены.

Шаг 3. Выбираем вершину 3. Рас­смотрим дугу (3, 4). Вершина 4 помечена. Переходим к следую­щей вершине — четвертой, соответствующая дуга — (4, 6). Вер­шина 6 не помечена. Присваиваем ей метку [4, 2]. Мы достигли вершины-стока, тем самым найдя путь (последовательность дуг), поток по которым можно увеличить. Информация об этом пути содержит метки вершин. В данном случае путь или увели­чивающаяся цепочка 1—> 2—> 4—> 6. Максимально возможный по­ток, который можно передать по дугам этого пути, определяет­ся второй цифрой метки вершины стока, то есть 2. Поток в сети стал равным 2.

Вторая итерация.

Шаг 1. Присвоим вершине 1 метку Рассмотрим дуги, нача­лом которых является помеченная вершина 1. Это дуги (1, 2) и (1, 3). Вершина 2 не может быть помечена, так как пропускная способность дуги (1, 2) исчерпана. Вершине 3 присваиваем метку [1, 6].

 

 

 

рис.14

Шаг 2. Выберем помеченную, но не просмотренную вершину. Это вершина 3. Повторяем действия. В результате вершина 4 получает метку [3, 2].

Шаг 3. Выбираем вершину 4, толь­ко она помечена и не просмотрена. Вершине 6 присваиваем метку [4, 1]. Почему только одна единица потока? На предыду­щей итерации израсходованы две единицы пропускной способ­ности данной дуги, осталась только одна. Вершина-сток достиг­нута. Найдена увеличивающая поток цепочка, это 1—> 3—»4-»6, по которой можно «протащить» единичный поток. Результиру­ющий поток в сети равен 3.

Третья итерация.

 

рис.15

Вершине 1 присваиваем метку [1, @].

Шаг 1. Результат — метка [1, 5] у вершины 3.

Шаг 2. Метка [3, 1] у вершины 4.

Шаг 3. Пропускная способность дуги (4, 6) израсходована полностью. Однако есть обратная дуга (2, 4), по которой передается по­ток, не равный нулю (обратите внимание на текст, выделенный курсивом — «изюминка» метода). Попробуем перераспреде­лить поток. Нам необходимо передать из вершины 4 поток, равный единице (зафиксирован в метке вершины). Задержим единицу потока в вершине 2, то есть вернем единицу потока из вершины 4 в вершину 2. Эту особенность зафиксируем в метке вершины 2 — [-4, 1]. Тогда единицу потока из вершины 4 мы передадим по сети вместо той, которая задержана в вершине 2, а единицу потока из вершины 2 попытаемся «протолкнуть» по сети, используя другие дуги. Итак, вершина 4 просмотрена, вершина 2 помечена, вершины 5 и 6 не помечены. Четвертый и пятый шаги очевидны. Передаем единицу потока из вершины 2 в вершину 6 через вершину 5. Вершина-сток достигнута, найде­на цепочка 1" 3" 4" 2" 5" 6, по которой можно передать по­ток, равный единице. При этом по прямым дугам поток увели­чивается на единицу, по обратным — уменьшается. Суммарный поток в сети — 4 единицы.

Четвертая итерация. Вершине 1 присваиваем метку

Шаг 1.

 

 

рис.16

Помечаем вершину 3 — [1, 4].

Шаг 2. Рас­сматриваем помеченную, но не просмотренную вер­шину 3. Одна дуга — (3, 4). Вершину 4 пометить не можем — пропускная спо­собность дуги исчерпана.

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

Итак, в чем суть «техники меток» Форда и Фалкерсона? Первое. На каждой итерации вершины сети могут находиться в одном из трех состояний: вершине присвоена метка, и она про­смотрена; вершине присвоена метка, и она не просмотрена, то есть не все смежные с ней вершины обработаны; вершина не имеет метки. Второе. На каждой итерации мы выбираем поме­ченную, но не просмотренную вершину v и пытаемся найти вершину и, смежную с о, которую можно пометить. Помечен­ные вершины, достижимые из вершины-источника, образуют множество вершин сети С. Если среди этих вершин окажется вершина-сток, то это означает успешный результат поиска це­почки, увеличивающей поток, при неизменности этого множе­ства работа заканчивается — поток изменить нельзя.

Алгоритм. Входные данные. Описание сети G=(V.E) матри­цей пропускных способностей С[ l.Jf, I~N], где N —.количество вершин. Вершина-источник s я вершина-сток t. Выходные дан ные. Поток, описываемый матрицей F[ 1.JJ.1.JfJ. Рабочие пере­менные. Структура данных для хранения меток — P[1..N, 1..2J. Элемент P[i, l ] — номер вершины, из которой можно передать поток, равный P[t, 2], в вершину с номером i. Логическая пере­менная Lg, значение True — есть цепочка, увеличивающая по­ток. False — нет.

Основная логика. Begin

< ввод данных и инициализация переменных (Lg: =True) >; While Lg Do Begin

FillChar (P, SizeOf (P), 0);

< процедура расстановки меток (Mark), если вершину t не смогли пометить, то Lg: =False; результат работы - значение Р (метки вершин) >;

If Lg Then < процедура Stream(t) - изменение потока по дугам найденной цепочки от вершины-стока t до вершины-источника s; входные данные - массив Р, результат - измененный массив F>; End;

< вывод потока F>; End.{конец обработки}

Уточним логику расстановки меток (не лучший вариант).

Procedure Mark; Var M: Set Of 1.. N;

i, l: integer; Begin

M: = [1..N]; (^Непросмотренные вершины.*} P(s, l]: =s; P[s, 2]: =maxint; {*Присвоим метку вершине-источнику. *}

l: =s;

While (P(t, l]=0) And Lg Do Begin For i: =l To N Do {*Поиск непомеченной вершины. *} If (P[i, l]=0) And ((C[l, i]< > 0) Or (C[i, l]< > 0)) Then

If F[l, i]< C[l, i] Then Beginf *Дуга прямая? *} P[ifl}: =l;

If P[l, 2]< C[l, i]-F[l, i] Then P[i, 2): =P[1, 2] Else P[i, 2]: =C[l, i]-F[l, i];

End Else

If F[i, l]> 0 Then Begin(*Дуга обратная? *) P[ifl}: =-1;

If P[l, 2}< F[i, l} Then P[i, 2]: =P{1, 2] Else P[i, 2]: =F[i, l]; End;

M: =M-[1]; {*Вершина с номером 1 просмотрена.*} 1: ml; {*Иаходим помеченную и непросмотренную вершину. *}

Repeat Inc(l)

Until (1> N) Or ((P[1, 1J< > 0) And (1 In M)); If 1> N Then Lg: =False; End; End;

Логика изменения потока F имеет вид:

Procedure Stream(q: Integer);

Begin {*Определяем тип дуги ~ прямая или обратная, знак минус у номера вершины - признак обратной дуги. *)

If P[q, D> 0 Then F[P(q, l], q]: =F(P[q, 1], q]+P[t, 2] Else F{q, abs(P[q, l))]: =F[q, abs(P[q, l]) ]-P(t, 2]; If Abs(P{q, 1])< > s Then Begin{*Если не

вершина-источник, то переход к предыдущей вершине цепочки. *} g: -Abs(P[q, lJ); Stream(q); End; End;

Итак, рассмотрение метода построения максимального пото­ка в сети завершено.