3. Потоки в транспортной сети

Пусть задан ориентированный грай без петель G (X, U), каж­дой дуге которого приписано неотрицательное вещественное число c(i, j) , называемое пропускной способностью дуги. В графе G име­ются две выделенные вершины s - исток и t - сток. Вершина s имеет только исходящие дуги, а t - входящие. Граф G называется транспортной сетью.

Определим на G функцию f , которая каждой дуге ставит в со­ответствие неотрицательное вещественное число f(i, j) c(i, j) , причем _i f(i, j) = _j f(i, j) для любого i s, t.

Функция f называется потоком в транспортной сети.

Обозначим через F_f величину потока, равную

F_f = _i f (s, i)

Необходимо найти поток в транспортной сети G имеющий максимальную величину.

Рассмотрим помечивающий алгоритм Форда-Фалкерсона, описываю­щий последовательное улучшение начального нулевого потока. Пусть в транспортной сети найден некоторый поток f . Если удается найти путь L из s в t. такой, что изменение f(i, j) для (i, j) L приводит к увеличению F_f , то строится поток f’ , .для которого F_{f ‘} < F_f Если такого пути L найти не удается, то поток f явля­ется максимальным.

Для построения пути L используется процедура помечивания вершин. Вершине, которая помечивается, приписывается пара (x, б). Первый символ в метке (x, б) указывает на вершину, которая непос­редственно предшествует данной вершине в пути L. Второй элемент б>0 определяет, на сколько возможно увеличить величину потока f, Путь L считается построенным, если помечена вершина t . Первой получает (-, Ґ) вершина s . Далее вершины помечаются по следующим правилам:

1)пусть вершина x помечена и имеется прямая дуга (x, y) причем f(x, y)<c(x,y).Тогда вершине y может быть приписана метка (x, min { б_x, c(x, y) – f(x, y)}) ;

2) пусть вершина x домечена и имеется обратная дуга (y, x) причем f(y, x) > 0. Тогда вершина y может быть приписана метка (x, min {б_x, f(y, x)}.

Помечиванием вершины t заканчивается построение f - допол­няющего пути L , всем вершинам которого приписаны метки.

В транспортной сети определяется новый поток f’ c F_{f ’} = F_f+б_t.

f(i, j)+б_t , если (i, j) – прямая дуга L

f’(i, j) = f(i, j)- б_t , если (i, j) – обратная дуга L

f(i, j) , если (i, j) U \ L .

Работа алгоритма заканчивается, если вершина i не помечена и не выполняется условие помечивания ни для одной вершины транспорт­ной сети при потоке f . Найденный поток f является максимальным.

В рассмотренном только что алгоритме выбор дополняющего пути (если он существует) осуществляется произвольным образом. Проил­люстрируем на примере проблему, к которой может привести произволь­ность выбора.

П ример 3. Рассмотрим транспортную сеть (рис.3), каждой дуге которой приписано число, являющееся пропускной способностью этой дуги (М – сколь угодно большое число). Рис 3.

Предположим, что мы начина­ем с нулевого потока и поочеред­но используем пути:

P₁ : s,a,b,t P₂ : s,b,a,t

в качестве дополняющих путей. На каждом ва­ге величина потока увеличивается точно на I, а максимальный поток величиной 2М достигается через 2М шагов, т.е. сложность алго­ритма не зависит от числа вершин и ребер в сети, а определяется функцией от пропускной способности М, которая может быть сколь угодно большой.

Целесообразно строить f - дополняющие пути таким образом, чтобы они были кратчайшими (в смысле числа дуг). Для этого доста­точно использовать дисциплину «первым пришел? - первым обслужен», т.е. сначала надо пытаться пометить смежные вершины той вершины, которая была раньше помечена. В этом случае сложность алгоритма не зависит от пропускных способностей дуг, а определяется только графом G .

Доказано [7], что если в алгоритме Форда-Фалкерсона каждое увеличение потока выполняется вдоль кратчайшего дополняющего пути, то максимальный поток можно получить не более, чем после m(n+2)/2 приращений величины потока, где m. - число дуг, n. - число вершин в транспортной сети.

Так как дополняющий путь можно найти за 0(m) шагов, то отсюда следует, что модифицированный алгоритм имеет сложность 0(m²*n).

Алгоритм 3.

начало

1) провести поиск в ширину и занумеровать вершины в соответ­ствии порядком их обхода при этом поиске;

2) положить f(u)=0 для всех к u U

3) V := S ;

4)  (s);= M ;

5) пока V  и не содержит t цикл ;

6) V := вершина с наименьшим номером в V ;

7) для всех x  Г^-1_v , не имеющих метки, цикл ;

8) если f(x, v) > 0 , то

9) xmin {(v), f (x, v)};

10) p(x) := v ;

11) l(x) := 0 ;

12) V := V  {x} ;

13) конец цикла;

14) для всех x Г_v не имеющих метки цикл ;

15) если f (v, x) < C (u, x) , то ;

16) (x) := min {(v), c(v, x)-f(v, x)} ;

17) p(x) := v ;

18) l(x) := 1 ;

19) V := V  {x} ;

20) конец цикла;

21) V := V \ {u} ;

22) конец цикла ;

23) если t V, то ;

24) начало ;

25) пока y S , цикл ;

26) y := t ;

27) если l(y) = 1 , то ;

29) y := p(y) ;

30) если l(y) = 0 , то,

31) f(y, p(y)) := f(y, p(y)) - (t) ;

32) y := p(y) ;

33) конец цикла ;

34) снять помечивание вершин и перейти к шагу 3 ;

35) конец ;

36) иначе f максимальный поток ;

конец.

Пример 4. Пусть для транспортной сети на рис.4 требуется най­ти максимальный поток. Пропускные способности дуг и значения пото­ка обозначены парами C(u) , f(u) возле соответствующей дуги u , f - дополняющие пути и построенная последовательность потоков показаны на рис.4-10. Максимальный поток изображен на рис.10.

Рис. 4 Рис. 5

Рис 6. Рис 7.

Р ис 8. Рис 9.

Р ис 10. Рис 11.

Таблица 17

Дуги Пропускные способности дуг

(s, a)	10	1	9	5	6	8	3	4	2	12
(s, b)	1	7	3	1	4	7	10	12	3	1
(s, c)	9	3	4	6	8	1	12	1	8	9
(a, b)	7	8	2	12	13	2	11	2	4	2
(a, d)	2	6	10	7	2	1	1	3	1	6
(a, t)	3	2	7	4	9	3	2	5	9	3
(b, d)	7	12	7	3	1	1	1	8	3	2
(b, e)	8	10	6	11	4	7	1	6	11	4
(c, b)	4	9	3	8	3	2	2	12	7	3
(c, e)	6	2	12	7	5	9	3	3	2	7
(c, t)	1	7	1	3	1	6	1	6	10	7
(d, e)	2	4	2	4	2	3	1	2	12	13
(d, t)	3	1	8	9	10	9	7	6	8	1
(e, t)	12	3	1	8	1	2	8	4	7	10

Контрольные вопросы и задания

1. Укажите последовательное изменение потока для транспортной сети, заданной графом на рис.11 и одним из столбцов табл.17.

2. Покажите, что для любого потока справедливо равенство:

_i f(s, i) = _jj, t) = F_f

3. Пропускная способность разреза R = <X₁, X₂> , s X₁ , t X₂ определяется следующим образом;

F_r =  _{xX1 , yX2} f(x, y)

Минимальным разрезом называется разрез, имеющий минимальную ‘ пропускную способность.

Покажите, что величина максимального потока равна пропускной способности минимального разреза.

4. Покажите, что в любой транспортной сети G с целочисленны­ми пропускными способноcтями существует максимальный поток f , в котором f(u) - целое число для любой дуги u в G .

5. Покажите, что если в транспортной сети не существует ориен­тированного пути из s в t , то величина максимального потока и пропускная способность минимального разреза равны нулю.

6. Предложите процедуру нахождения дуги, увеличение пропуск­ной способности которой приводит к увеличению максимального потока.

7. Предложите процедуру нахождения дуг в транспортной сети, уменьшение пропускных способностей которых не приводит к уменьше­нию максимального потока.

8. Сформулируйте задачу нахождения максимального потока как задачу линейного программирования.