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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



Алгоритм построения максимального потока в транспортной сети D:

Шаг 1. Полагаем i = 0. Пусть j0 - любой допустимый поток в транспортной сети D. (например, полный; можно начинать с нулевого потока: j0 (x), x Î X).

Шаг 2. По сети D и потоку ji строим орграф приращений I(D, ji).

Шаг 3. Находим простую цепь hi, являющуюся минимальным путем из v1 в vn в нагруженном орграфе I(D, ji) (например, используя алгоритм Форда - Беллмана). Если длина этой цепи равна ¥, то поток ji максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи hi на максимально допустимую величину ai > 0, где ai Î Z (прибавляя ее для каждой дуги x Î X, через которую проходит цепь hi, к уже имеющейся величине потока по дуге x, если направления x и hi совпадают, и, вычитая, если направления x и hi противоположны).

Пример 92.

Выяснить является ли полный поток максимальным (рис. 51), если нет, то дополнить его до максимального.

 

Решение.

Для решения используем алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе.

Построим матрицу длин дуг C(D) и l -матрицу (табл. 69).

Таблица 69

  v1 v2 v3 v4 v5 v6  
v1 ¥ ¥   ¥ ¥ ¥              
v2   ¥ ¥ ¥   ¥   ¥ ¥        
v3     ¥     ¥   ¥          
v4 ¥     ¥ ¥     ¥ ¥ ¥ ¥ ¥  
v5 ¥     ¥ ¥     ¥ ¥ ¥      
v6 ¥ ¥ ¥     ¥   ¥ ¥ ¥ ¥    

Поскольку , то существует нулевой путь из источника v1 в сток v6. Значит, полный поток не является максимальным. Дополним его до максимального. Для этого найдем путь нулевой длины:

Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех нулевых путей из v1 в v6 в орграфе приращений равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5, где i1 = 6.

Получаем, что в качестве такой последовательности надо взять номера 1, 3, 2, 5, 6, так как

Тогда v1v3v2v5v6 – искомый нулевой путь из v1 в v6. Дуги, совпадающие по направлению с дугами исходной транспортной сети помечаем знаком «+», не совпадающие – знаком «-».

Получаем, Теперь необходимо найти величину, которую будем перемещать по полученному контуру. Для этого, каждому ребру в контуре поставим в соответствие число a(i, j), которое находим по следующему правилу: если направление ребра (i, j) в контуре совпадает с направлением ребра x в транспортной сети, то a(i, j)=с(х)-j(х); если направление ребра в контуре не совпадает с направлением ребра в транспортной сети, то a(i, j)=j(х). Итак, из чисел a(i, j) найдем минимальное:

min{8-2=6, 2, 6-2=4, 9-4=5}=2.

Перемещаем по контуру 2.

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

Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 11. Проверим, является ли он максимальным.

Построим матрицу длин дуг C(D) и l -матрицу (табл. 70).

Таблица 70

  v1 v2 v3 v4 v5 v6  
v1 ¥ ¥   ¥ ¥ ¥              
v2   ¥   ¥   ¥   ¥ ¥ ¥ ¥ ¥ ¥
v3   ¥ ¥ ¥ ¥ ¥   ¥          
v4 ¥     ¥ ¥     ¥ ¥ ¥ ¥ ¥ ¥
v5 ¥     ¥ ¥     ¥ ¥ ¥ ¥ ¥ ¥
v6 ¥ ¥ ¥     ¥   ¥ ¥ ¥ ¥ ¥ ¥

Так как , то нулевого пути из v1 в v6 не существует. Значит, поток является максимальным.

 



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 150; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.147.102.111 (0.006 с.)