Алгоритм Форда-Фалкерсона. Поток в сети.

Определение 1:

          Сетью называется связный орграф без петель.

Определение 2:

          Потоком в сети называется некоторая функция, которая ставит в соответствие дуге некоторое число-вес дуги.

Для определения потока в сети используют алгоритм Форда-Фалкерсона:

а) ищем любую цепь из истока графа в сток;

б) каждой дуге приписываем возможный больший поток из истока в сток (записываем его через дробь с весом дуги; при этом поток не может превысить вес дуги, но может быть ему равен);

в) если поток становится равен весу дуги, то эта дуга является насыщенной, то есть через нее нельзя пройти при рассмотрении цепей в графе;

г) так перебираем все возможные цепи, пока станет невозможно попасть из истока в сток;

д) поток  в сети будет равен сумме потоков всех дуг, инцидентных стоку графа (следует заметить, что сумма потоков всех дуг, инцидентных стоку графа равна сумме потоков всех дуг, инцидентных истоку графа).

Задача 9.17

Дана сеть. Определить поток в сети.

Решение:

Следуя вышеописанному алгоритму, рассмотрим следующие цепи:

1-5-9-13-14;

1-4-8-12-14;

1-3-7-11-14;

1-2-6-10-14

Расставив потоки у соответствующих дуг, получим:

Далее будем выбирать цепи так, чтобы насыщались дуги, инцидентные истоку.

1-4-9-13-12-14 (здесь поток каждой дуги увеличивается на единицу);

1-4-9-8-13-12-14 (здесь также на единицу);

1-4-9-8-13-12-11-14 (и здесь тоже на единицу).

После этой последовательности цепей получим насыщенную дугу 1-4.

 

Следующая последовательность цепей дает нам окончательный результат:

1-3-4-9-8-13-12-11-14 (здесь поток каждой дуги увеличивается на двойку);

1-2-3-4-9-8-13-12-11-14 (здесь поток каждой дуги опять увеличивается на двойку).

Поток в сети равен 4+9+7+6=6+6+8+6=26.

Насыщенные дуги: 1-4,1-3,1-2, 5-9, 9-13, 13-14, 13-12, 4-8, 8-12, 12-14, 3-7, 11-14, 2-6, 3-4.

Программа к задаче:

> restart:with(networks):

> new(G):V:=$1..14:addvertex([V],G):

> v1:=1:#источник

> v2:=14:#сток

> E:=[[1,5],[1,4],[1,3],[1,2],[2,3],[2,6],[3,4],[3,7],[4,8],[4,9],[4,5],[5,9],[6,10],[6,3],[7,4],[7,11],[7,6],[8,7],[8,12],[8,13],[9,13],[9,8],[10,14],[10,7],[11,10],[11,8],[11,14],[12,14],[12,11],[13,12],[13,14]]:

> w:=[9,8,6,6,3,4,4,4,5,10,3,6,5,9,10,5,8,8,5,12,7,7,6,10,8,12,9,7,8,7,6]:

> addedge(E,weights=w,G):

> potok=flow(G,v1,v2,ed);