Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
МЕТОД УКАЗАНИЯ ПО МАТ МЕТОДАМ 2011 2012.doc
Скачиваний:
8
Добавлен:
25.11.2018
Размер:
775 Кб
Скачать
☆

Приложение г Методика нахождения максимального потока в графе по алгоритму Форда-Фалкерсона

Предварительный шаг.

Записываем пропускные способности дуг сети в таблицу размерности (n+1)x(n+1), где n+1 – количество вершин сети G(E,e). Если пропускная способность дуги (Ei, Ej) больше нуля, а симметричной ей дуги (Ej, Ei) равна нулю, то в клетку (i,j) заносим bij , а в клетку (j,i) – нуль; если bij=bji=0, то клетки (i,j) (j,i) не заполняем

  1. Находим по таблице путь из E0 в En с пропускной способностью больше нуля. Для этого столбец, соответствующий вершине E0 помечаем знаком *. Отыскиваем в E0 –й строке элементы b0j>0 и столбцы, в которых они находятся, помечаем сверху номером просматриваемой строки (цифрой 0). В результате окажутся выделенными все дуги (E0, Ej) с положительной пропускной способностью. Эти дуги могут служить первыми дугами пути из E0 в En.

Далее просматриваем те строки, номера которых совпадают с номерами помеченных столбцов. В каждой такой строе, например Ei-й отыскиваем элементы bij больше нуля находящиеся в непомеченных столбцах, и помечаем эти столбцы номером просматриваемой сроки. Таким образом, окажутся выделенными дуги, которые могут служить вторыми дугами путей из E0 в En

Продолжаем аналогичный просмотр строк, номера которых совпадают с номерами помеченных столбцов, до тех пор, пока:

    1. либо не будет помечен столбец En (сток). Это означает, что удалось выделить путь с пропускной способностью больше нуля из E0 в En. В этом случае искомый путь находим, используя пометки столбцов. Пусть последняя вершина пути En помечена номером k. По этой метке находим предшествующую вершину Ek (при просмотре Ek был помечен столбец En, и дуга (Ek, En) – последняя в искомом пути). Элемент bkn>0, стоящий на пересечении Ek-й строки и En-го столбца, отмечаем знаком минус (получим b-kn ), а симметричный ему элемент bnk , находящийся на пересечении En –й строки и – Ek го столбца ,- знаком плюс (получим b+nk ). Так как просматривалась Ek- я строка, то перед этим был помечен, например, номером r , Ek- й столбец. Поэтому двигаясь от элемента b+nk по Ek-му столбцу до r-й строки (дуга (Er, Ek) предшествует дуге (Ek, En)) и отмечаем brk знаком минус, bkr – знаком плюс. Продолжаем этот процесс до тех пор, пока не придем к E0-й строке и не отметим знаком минус элемент этой строки и знаком плюс – симметричный ему элемент. Переходим к п. 2.

    2. Либо нельзя будет пометить новые столбцы ( в просматриваемых строках не окажется положительных элементов, расположенных в непомеченных столбцах). В этом случае отсутствует путь из E0 в En, проходящий по дугам с положительной пропускной способностью и общий повторяющийся шаг законен

  1. Находим пропускную способность найденного пути , т.е. максимальное количество вещества, которое можно переместить из E0 в En по пути в единицу времени. Пропускная способность пути равна наименьшей из пропускных способностей дуг, входящих в этот путь, т.е. .

  2. Определяем остаточные пропускные способности дуг найденного пути и симметричных к ним. Для этого из элементов таблицы b-il вычитаем , а к элементам b+il прибавляем . В результате выполнения этого действия получим новую таблицу, аналогичную исходной, но с измененными пропускными способностями. Перейти к п.1, который применяем до тех пор, пока не получим окончательную таблицу, в которой нет ни одного пути из E0 в En с пропускной способностью больше нуля