Узнай об автоматике все - читай kip-help.narod.ru |
Хочешь узнать ответ на свой вопрос? Напиши в редакцию! |
|
Алгоритм Форда-Фалкерсона для нахождения максимального потока | Письмо в редакцию |
в сети Теорема Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе). В любой сети существует максимальный поток. Величина максимального потока равна пропускной способности минимального разреза. Теорема Форда-Фалкерсона 2. Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез (X,X), где X-множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность. Описание алгоритма Пусть изначально в сети имеется поток f (допустим с нулевыми значениями на всех дугах). Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети состоит из двух процедур: 1) Процедура помечивания вершин 2) Процедура изменения потока 1) Процедура помечивания вершин. Обработка i-й вершины с пометкой (x,e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу: - если дуга направлена из i в j и поток по этой дуге (fij) меньше пропускной способности дуги (cij), то вершине j присваивается метка (i+,min(e,cij-fij)) - если дуга направлена из j в i и поток по этой дуге (fji) больше нуля, то вершине j присваивается метка (i-,min(e,fji)) Эта процедура всегда начинается с помечивания и обработки истока. Он помечается особой меткой (-,¥). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т.д. Процесс помечивания заканчивается в двух случаях: 1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это значит, что найденный поток - максимальный и алгоритм останавливается. 2) Помечается сток. В этом случае производится изменение потока. 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. Область разреза между помеченными при последнем помечивании вершинами и непомеченными имеет минимальную пропускную способность. |
||
Научись самостоятельно изготавливать электронные устройства с сайтом radiohlam.ru
|
||
Решим для вас задачи по математике, физике, тау, программированию... |
||
|
© 2007 Материалы сайта охраняются законом об авторском праве |