Алгоритм Форда-Фалкерсона для нахождения
Максимального потока в сети
Теорема Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе).
В любой сети существует максимальный поток. Величина максимального потока равна пропускной способности минимального разреза.
Теорема Форда-Фалкерсона 2.
Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез (X,X), где X-множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность.
Описание алгоритма
Пусть изначально в сети имеется поток f (допустим с нулевыми значениями на всех дугах).
Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети состоит из двух процедур:
1) Процедура помечивания вершин
2) Процедура изменения потока
Процедура помечивания вершин.
Обработка i-й вершины с пометкой (x,e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу:
- если дуга направлена из i в j и поток по этой дуге (fij) меньше пропускной способности дуги (cij), то вершине j присваивается метка (i+,min(e,cij-fij))
- если дуга направлена из j в i и поток по этой дуге (fji) больше нуля, то вершине j присваивается метка (i-,min(e,fji))
Эта процедура всегда начинается с помечивания и обработки истока. Он помечается особой меткой (-,¥). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т.д.
Процесс помечивания заканчивается в двух случаях:
1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это значит, что найденный поток - максимальный и алгоритм останавливается.
2) Помечается сток. В этом случае производится изменение потока.
Процедура изменения потока.
Если сток получил метку (k+,d), то потоки будут изменяться на величину d следующим образом:
- если мы находимся в вершине j с меткой (i+,x), то прибавляем d к fij и переходим в вершину i.
- если мы находимся в вершине j с меткой (i-,x), то вычитаем d из fij и переходим в вершину i.
Изменение потока начинается от стока и продолжается до достижения истока. После этого все метки стираются и заново выполняется процедура помечивания вершин.
Этот процесс продолжается до тех пор, пока не будет найден максимальный поток (ни одну вершину больше нельзя пометить, но сток не помечен).
Пример:
Вычислим максимальный поток для изображенной ниже сети.
Здесь первое число в скобках - пропускная способность дуги, второе число - поток (в начальный момент берем поток равный нулю)
1) Помечивание вершин
Исток i получает метку (-,¥).
Для смежной с i непомеченной вершины a1 имеем:
дуга направлена из i в a1, 0<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-0))=(i+,7)
Для смежной с i непомеченной вершины a2 имеем:
дуга направлена из i в a2, 0<6, следовательно присваиваем вершине a2 метку (i+,min(¥,6-0))=(i+,6)
После обработки вершины i мы пометили еще две вершины a1 и a2. Дальнейшую обработку можно начинать с любой необработанной помеченной вершины. Рассмотрим сначала вершину a2.
Для смежной с a2 непомеченной вершины a4 имеем:
дуга направлена из a4 в a2, поток равен нулю, следовательно метку вершине a4 не присваиваем
Для смежной с a2 непомеченной вершины s имеем:
дуга направлена из a2 в s, 0<9, следовательно присваиваем вершине s метку (a2+,min(6,9-0))=(a2+,6)
В процессе обработки вершины a2 у нас пометился сток, поэтому переходим к процедуре изменения потока. На рисунке изображены помеченные вершины.
2) Изменение потока
Сток получил метку (a2+,6), следовательно потоки будут изменяться на 6.
Начинаем со стока:
Мы находимся в вершине s с пометкой (a2+,6), следовательно изменяем поток из вершины a2 в вершину s. Новое значение потока 0+6=6, и переходим в вершину a2.
Вершина a2 имеет метку (i+,6), следовательно изменяем поток из вершины i в вершину a2. Новое значение потока 0+6=6, и переходим в вершину i.
Мы вернулись к истоку => процедура изменения потоков закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.
На рисунке изображена сеть, после первого изменения потоков.
3) Помечивание вершин
Исток i получает метку (-,¥).
Для смежной с i непомеченной вершины a1 имеем:
дуга направлена из i в a1, 0<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-0))=(i+,7)
Для смежной с i непомеченной вершины a2 имеем:
дуга направлена из i в a2, 6=6, следовательно вершине a2 метку не присваиваем
Переходим к обработке вершины a1.
Для смежной с a1 непомеченной вершины a3 имеем:
дуга направлена из a1 в a3, 0<6, следовательно присваиваем вершине a3 метку (a1+,min(7,6-0)=(a1+,6)
Переходим к обработке вершины a3.
Для смежной с a3 непомеченной вершины s имеем:
дуга направлена из a3 в s, 0<4, следовательно присваиваем вершине s метку (a3+,min(6,4-0))=(a3+,4)
В процессе обработки вершины a3 у нас пометился сток, поэтому переходимк процедуре изменения потока. На рисунке изображены помеченные вершины.
4) Изменение потока
Сток получил метку (a3+,4), следовательно потоки будут изменяться на 4.
Начинаем со стока:
Мы находимся в вершине s с пометкой (a3+,4), следовательно изменяем поток из вершины a3 в вершину s. Новое значение потока 0+4=4 и переходим в вершину a3.
Вершина a3 имеет пометку (a1+,6), следовательно изменяем поток из вершины a1 в вершину a3. Новое значение потока 0+4=4 и переходим в вершину a1.
Вершина a1 имеет пометку (i+,7), следовательно изменяем поток из вершины i в вершину a1. Новое значение потока 0+4=4 и переходим в вершину i.
Мы вернулись к истоку => процедура изменения потоков закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.
На рисунке изображена сеть после второго изменения потоков.
5) Помечивание вершин
Исток i получает метку (-,¥).
Для смежной с i непомеченной вершины a1 имеем:
дуга направлена из i в a1, 4<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-4))=(i+,3)
Для смежной с i непомеченной вершины a2 имеем:
дуга направлена из i в a2, 6=6, следовательно вершине a2 метку не присваиваем
Переходим к обработке вершины a1.
Для смежной с a1 непомеченной вершины a3 имеем:
дуга направлена из a1 в a3, 4<6, следовательно присваиваем вершине a3 метку (a1+,min(3,6-4))=(a1+,2)
Переходим к обработке вершины a3.
Для смежной с a3 непомеченной вершины s имеем:
дуга направлена из a3 в s, 4=4, следовательно вершине s метку не присваиваем
Для смежной с a3 непомеченной вершины a4 имеем:
дуга направлена из a3 в a4, 0<3, следовательно присваиваем вершине a4 метку (a3+,min(2,3-0))=(a3+,2)
Переходим к обработке вершины a4.
Для смежной с a4 непомеченной вершины a2 имеем:
дуга направлена из a4 в a2, 0<2, следовательно присваиваем вершине a2 метку (a4+,min(2,2-0))=(a4+,2)
Переходим к обработке вершины a2.
Для смежной с a2 непомеченной вершины s имеем:
дуга направлена из a2 в s, 6<9, следовательно присваиваем вершине s метку (a2+,min(2,9-6))=(a2+,2)
В процессе обработки вершины a2 у нас пометился сток, поэтому переходим к процедуре изменения потока. На рисунке изображены помеченные вершины.
6) Изменение потока
Сток получил метку (a2+,2), следовательно потоки будут изменяться на 2.
Начинаем со стока:
Мы находимся в вершине s с пометкой (a2+,2), следовательно изменяем поток из вершины a2 в вершину s. Новое значение потока 6+2=8 и переходим в вершину a2.
Вершина a2 имеет пометку (a4+,2), следовательно изменяем поток из вершины a4 в вершину a2. Новое значение потока 0+2=2 и переходим в вершину a4.
Вершина a4 имеет пометку (a3+,2), следовательно изменяем поток из вершины a3 в вершину a4. Новое значение потока 0+2=2 и переходим в вершину a3.
Вершина a3 имеет пометку (a1+,2), следовательно изменяем поток из вершины a1 в вершину a3. Новое значение потока 4+2=6 и переходим в вершину a1.
Вершина a1 имеет пометку(i+,3), следовательно изменяем поток из вершины i в вершину a1. Новое значение потока 4+2=6 и переходим в вершину i.
Мы вернулись к истоку => процедура изменения потока закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.
На рисунке изображена сеть после третьего изменения потоков.
7) Помечивание вершин
Исток i получает метку (-,¥).
Для смежной с i непомеченной вершины a1 имеем:
дуга направлена из i в a1, 6<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-6))=(i+,1)
Для смежной с i непомеченной вершины a2 имеем:
дуга направлена из i в a2, 6=6, следовательно вершине a2 метку не присваиваем
Переходим к обработке вершины a1.
Для смежной с a1 непомеченной вершины a3 имеем:
дуга направлена из a1 в a3, 6=6, следовательно вершине a3 метку не присваиваем
Теперь у нас обработаны все помеченные вершины, но остался непомеченным сток.
Это означает, что полученный поток и есть максимальный. При последнем помечивании мы пометили вершины i и a1. Область разреза между помеченными при последнем помечивании вершинами и непомеченными имеет минимальную пропускную способность.
