Процедура изменения потока.

Теорема Форда-Фалкерсона 2.

Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез (X,X), где X-множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность.

Описание алгоритма

Пусть изначально в сети имеется поток f (допустим с нулевыми значениями на всех дугах).

Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети состоит из двух процедур:

1) Процедура помечивания вершин

2) Процедура изменения потока

Процедура помечивания вершин.

Обработка i-й вершины с пометкой (x,e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу:

- если дуга направлена из i в j и поток по этой дуге (f_ij) меньше пропускной способности дуги (c_ij), то вершине j присваивается метка (i⁺,min(e,c_ij-f_ij))

- если дуга направлена из j в i и поток по этой дуге (f_ji) больше нуля, то вершине j присваивается метка (i^-,min(e,f_ji))

Эта процедура всегда начинается с помечивания и обработки истока. Он помечается особой меткой (-,¥). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т.д.

Процесс помечивания заканчивается в двух случаях:

1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это значит, что найденный поток - максимальный и алгоритм останавливается.

2) Помечается сток. В этом случае производится изменение потока.

Процедура изменения потока.

Если сток получил метку (k⁺,d), то потоки будут изменяться на величину d следующим образом:

- если мы находимся в вершине j с меткой (i⁺,x), то прибавляем d к f_ij и переходим в вершину i.

- если мы находимся в вершине j с меткой (i^-,x), то вычитаем d из f_ij и переходим в вершину i.

Изменение потока начинается от стока и продолжается до достижения истока. После этого все метки стираются и заново выполняется процедура помечивания вершин.

Этот процесс продолжается до тех пор, пока не будет найден максимальный поток (ни одну вершину больше нельзя пометить, но сток не помечен).

Пример:

Вычислим максимальный поток для изображенной ниже сети.

Здесь первое число в скобках - пропускная способность дуги, второе число - поток (в начальный момент берем поток равный нулю)

1) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a₁ имеем:

дуга направлена из i в a₁, 0<7, следовательно присваиваем вершине a₁ метку (i⁺,min(¥,7-0))=(i⁺,7)

Для смежной с i непомеченной вершины a2 имеем:

дуга направлена из i в a₂, 0<6, следовательно присваиваем вершине a₂ метку (i⁺,min(¥,6-0))=(i⁺,6)

После обработки вершины i мы пометили еще две вершины a₁ и a₂. Дальнейшую обработку можно начинать с любой необработанной помеченной вершины. Рассмотрим сначала вершину a₂.

Для смежной с a₂ непомеченной вершины a₄ имеем:

дуга направлена из a₄ в a₂, поток равен нулю, следовательно метку вершине a₄ не присваиваем

Для смежной с a₂ непомеченной вершины s имеем:

дуга направлена из a₂ в s, 0<9, следовательно присваиваем вершине s метку (a₂⁺,min(6,9-0))=(a₂⁺,6)

В процессе обработки вершины a2 у нас пометился сток, поэтому переходим к процедуре изменения потока. На рисунке изображены помеченные вершины.

2) Изменение потока

Сток получил метку (a₂⁺,6), следовательно потоки будут изменяться на 6.

Начинаем со стока:

Мы находимся в вершине s с пометкой (a₂⁺,6), следовательно изменяем поток из вершины a₂ в вершину s. Новое значение потока 0+6=6, и переходим в вершину a₂.

Вершина a₂ имеет метку (i⁺,6), следовательно изменяем поток из вершины i в вершину a₂. Новое значение потока 0+6=6, и переходим в вершину i.

Мы вернулись к истоку => процедура изменения потоков закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.

На рисунке изображена сеть, после первого изменения потоков.

3) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a₁ имеем:

дуга направлена из i в a₁, 0<7, следовательно присваиваем вершине a₁ метку (i⁺,min(¥,7-0))=(i⁺,7)

Для смежной с i непомеченной вершины a₂ имеем:

дуга направлена из i в a₂, 6=6, следовательно вершине a₂ метку не присваиваем

Переходим к обработке вершины a₁.

Для смежной с a₁ непомеченной вершины a₃ имеем:

дуга направлена из a₁ в a₃, 0<6, следовательно присваиваем вершине a₃ метку (a₁⁺,min(7,6-0)=(a₁⁺,6)

Переходим к обработке вершины a₃.

Для смежной с a₃ непомеченной вершины s имеем:

дуга направлена из a₃ в s, 0<4, следовательно присваиваем вершине s метку (a₃⁺,min(6,4-0))=(a₃⁺,4)

В процессе обработки вершины a₃ у нас пометился сток, поэтому переходимк процедуре изменения потока. На рисунке изображены помеченные вершины.

4) Изменение потока

Сток получил метку (a₃⁺,4), следовательно потоки будут изменяться на 4.

Начинаем со стока:

Мы находимся в вершине s с пометкой (a₃⁺,4), следовательно изменяем поток из вершины a₃ в вершину s. Новое значение потока 0+4=4 и переходим в вершину a₃.

Вершина a₃ имеет пометку (a₁⁺,6), следовательно изменяем поток из вершины a₁ в вершину a₃. Новое значение потока 0+4=4 и переходим в вершину a₁.

Вершина a₁ имеет пометку (i⁺,7), следовательно изменяем поток из вершины i в вершину a₁. Новое значение потока 0+4=4 и переходим в вершину i.

Мы вернулись к истоку => процедура изменения потоков закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.

На рисунке изображена сеть после второго изменения потоков.

5) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a₁ имеем:

дуга направлена из i в a₁, 4<7, следовательно присваиваем вершине a₁ метку (i⁺,min(¥,7-4))=(i⁺,3)

Для смежной с i непомеченной вершины a₂ имеем:

дуга направлена из i в a₂, 6=6, следовательно вершине a₂ метку не присваиваем

Переходим к обработке вершины a₁.

Для смежной с a₁ непомеченной вершины a₃ имеем:

дуга направлена из a₁ в a₃, 4<6, следовательно присваиваем вершине a₃ метку (a₁⁺,min(3,6-4))=(a₁⁺,2)

Переходим к обработке вершины a₃.

Для смежной с a₃ непомеченной вершины s имеем:

дуга направлена из a₃ в s, 4=4, следовательно вершине s метку не присваиваем

Для смежной с a₃ непомеченной вершины a₄ имеем:

дуга направлена из a₃ в a₄, 0<3, следовательно присваиваем вершине a₄ метку (a₃⁺,min(2,3-0))=(a₃⁺,2)

Переходим к обработке вершины a₄.

Для смежной с a₄ непомеченной вершины a₂ имеем:

дуга направлена из a₄ в a₂, 0<2, следовательно присваиваем вершине a₂ метку (a₄⁺,min(2,2-0))=(a₄⁺,2)

Переходим к обработке вершины a₂.

Для смежной с a₂ непомеченной вершины s имеем:

дуга направлена из a₂ в s, 6<9, следовательно присваиваем вершине s метку (a₂⁺,min(2,9-6))=(a₂⁺,2)

В процессе обработки вершины a₂ у нас пометился сток, поэтому переходим к процедуре изменения потока. На рисунке изображены помеченные вершины.

6) Изменение потока

Сток получил метку (a₂⁺,2), следовательно потоки будут изменяться на 2.

Начинаем со стока:

Мы находимся в вершине s с пометкой (a₂⁺,2), следовательно изменяем поток из вершины a₂ в вершину s. Новое значение потока 6+2=8 и переходим в вершину a₂.

Вершина a₂ имеет пометку (a₄⁺,2), следовательно изменяем поток из вершины a₄ в вершину a₂. Новое значение потока 0+2=2 и переходим в вершину a₄.

Вершина a₄ имеет пометку (a₃⁺,2), следовательно изменяем поток из вершины a₃ в вершину a₄. Новое значение потока 0+2=2 и переходим в вершину a₃.

Вершина a₃ имеет пометку (a₁⁺,2), следовательно изменяем поток из вершины a₁ в вершину a₃. Новое значение потока 4+2=6 и переходим в вершину a₁.

Вершина a₁ имеет пометку(i⁺,3), следовательно изменяем поток из вершины i в вершину a₁. Новое значение потока 4+2=6 и переходим в вершину i.

Мы вернулись к истоку => процедура изменения потока закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.

На рисунке изображена сеть после третьего изменения потоков.

7) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a₁ имеем:

дуга направлена из i в a₁, 6<7, следовательно присваиваем вершине a₁ метку (i⁺,min(¥,7-6))=(i⁺,1)

Для смежной с i непомеченной вершины a₂ имеем:

дуга направлена из i в a₂, 6=6, следовательно вершине a₂ метку не присваиваем

Переходим к обработке вершины a₁.

Для смежной с a₁ непомеченной вершины a₃ имеем:

дуга направлена из a₁ в a₃, 6=6, следовательно вершине a₃ метку не присваиваем

Теперь у нас обработаны все помеченные вершины, но остался непомеченным сток.

Это означает, что полученный поток и есть максимальный. При последнем помечивании мы пометили вершины i и a₁. Область разреза между помеченными при последнем помечивании вершинами и непомеченными имеет минимальную пропускную способность.

Дата добавления: 2015-07-14