Рассмотрим алгоритм Форда-Фалкерсона определение максимального потока.

Шаг 0. Пусть источники помечены но не просмотрены, а все остальные узлы не помечены.

Шаг 1. Выбрать любой помеченный, но не просмотренный узел i.

Шаг 2. Просмотреть все дуги e (i, j) с пропускной способностью a _е > 0, соединяющие узел i с еще не помеченными узлами j. Приписать пометки узлам j и отметить дуги e _j = e = (i, j).Теперь узел i помечен и просмотрен, узлы j помечены, но не просмотрены. Если при этом сток оказался помеченным, то необходимая цепь найдена. В противном случае после просмотра по всем дугам (i, j) перейти к шагу 3.

Шаг 3. Пусть узел i помечен и просмотрен. Перейти к шагу 1 и повторять шаги алгоритма до тех пор, пока не останется помеченных и не просмотренных узлов. На этом поиск максимального потока заканчивается.

Рассмотрим пример.

7.7 I

c e

16 I 9.8 I 12 7 I

I 8.8 I d I

s a I 11 I j

12.1 12 I 5

f

6.2 I 11 I 15 I 20 I

I

b t

I

Обозначено: I - ресурсы не использованы

R - ресурсы использованы полностью

IR - ресурсы использованы частично

1. Выбираем какой - то один из произвольных потоков.

p1 = min {f(s, b), f(b, t)} = min {6.2; 8} = 6.2;

I

c e

I

I I d I

I

s a I j

I I I

f

R I I

I

b t

IR

2. Маршрут (s, a), (a, f), (f, t);

p2 = min {f(s, a), f(a, f), f(f, t)} = min {12.1; 12; 15} = 12;

P_S[AK1] = 18.2;

I

c e

I

I I d I

I

s a I j

IR R I

f

R I I IR I

b t IR

3. Маршрут (s,a), (a,b), (b,f), (f,t);

p3 = min {f(s,a), f(a,b), f(b,f), f(f,t)} = min {0.1; 11; 7.5; 3} = 7.5;

P_S = 18.3;

I

c e

I

I I d I

I

s a I j

IR R I

f

R IR IR I

R

B t

IR

4.Маршрут (s, a), (a, b), (b, t);

p4 = min {f(s, c), f(c, e), f(e, j), f(j, t)} = min {16; 7.7; 7, 20} = 7;

P_S = 25.3;

I

c e

I

I I d I

I

s a I j

IR R I

f

R IR IR I

R в t

R

Таким образом, максимальный поток составит 25.3 единицы.

Если для сети каждое ребро характеризуется некоторым числом, которое является расстоянием между узлами сети, то возникает задача определения кратчайшего расстояния между заданными узлами, которые называются истоком и стоком

6.2 7.5 15 20

b t

Сток

1. Окрасим вершину s.

Положим d(s) = 0;

d(a) = d(b) = d(c) = d(e) =d(f) = d(j) =¥;

2. Текущая переменная y = s ;

d(a) = min { d(a), d(s) + d(s,a)} = min {¥; 0 + 12.1} = 12.1;

d(b) = min {d(b), d(s) + d(s,b)} = min {¥; 0 + 6.2} = 6.2;

d(c) = min {d(c), d(s) + d(s,c)} = min {¥; 0 + 16 } = 16;

d(d) = min {d(d), d(s) + d(s,d)} = min {¥; 0 + ¥ } = ¥;

d(e) = min {d(e), d(s) + d(s,e)} = min {¥; 0 + ¥ } = ¥;

d(f) = min {d(f), d(s) + d(s,f)} = min {¥; 0 + ¥ } = ¥;

d(j) = min {d(j), d(s) + d(s,j)} = min {¥; 0 + ¥ } = ¥;

d(t) = min {d(t), d(s) + d(s,t)} = min {¥; 0 + ¥ } = ¥;

min {d(a), d(b), d(c), d(d), d(e), d(f), d(j),d(t)} =

= min {12.1; 6.2; 16; ¥; ¥; ¥; ¥; ¥} = 6.2; d(b) = 6.2 ;

Окрашиваем вершину b.

s

b

3. Текущая переменная y = b;

d(a) = min {d(a), d(b) + d(b,a)} = min {12.1; 6.2 + ¥} = 12.1;

d(c) = min {d(c), d(b) + d(b,c)} = min {16; 6.2 + ¥} = 16;

d(d) = min {d(d), d(b) + d(b,d)} = min {¥; 6.2 + ¥} = ¥;

d(e) = min {d(e), d(b) + d(b,e) } = min {¥; 6.2 + ¥} = ¥;

d(f) = min {d(f), d(b) + d(b,f) } = min {¥; 6.2 + 7.5} = 13.7;

d(j) = min {d(j), d(b) + d(b,j) } = min {¥; 6.2 + ¥} = ¥;

d(t) = min {d(t), d(b) + d(b,t) } = min {¥; 6.2 + 8} = 14.2;

min {d(a), d(c), d(d), d(e), d(f0, d(j),d(t)} =

= min {12.1; 16; ¥; ¥; 13.7; ¥; ¥} = 12.1; d(a) = 12.1;

Окрашиваем вершину a.

s a

b

4. Текущая переменная y = a;

d(c) = min {d(c), d(a) + d(a,c)} = min {16; 12.1 + 9.8} = 16;

d(d) = min {d(d), d(a) + d(a,d)} = min {¥; 12.1 + 8.8} = 20.9;

d(e) = min {d(e), d(a) + d(a,e)} = min {¥; 12.1 + ¥} = ¥;

d(f) = min {d(f), d(a) + d(a,f)} = min {13.7; 12.1 + 12} = 13.7;

d(j) = min {d(j), d(a) + d(a,j)} = min {¥; 12.1 +¥} = ¥;

d(t) = min {d(t), d(b)+d(b,t)} = min {¥; 12.1 + ¥, 6.2+8} = 14.2;

min {d(c), d(d), d(e), d(f), d(j),d(t)} =

= min {16; 20.9; ¥; 13.7; ¥; ¥} =13.7; d(f) = 13.7;

Окрашиваем вершину f.

s a

f

b

5. Текущая переменная y = f ;

d(c) = min {d(c), d(f) + d(f,c)} = min {16; 13.7 + ¥} = 16;

d(d) = min {d(d), d(f) + d(f,d)} = min {20.9; 13.7 + ¥} = 20.9;

d(e) = min {d(e), d(f) + d(f,e)} = min {¥; 13.7 + ¥} = ¥;

d(j) = min {d(j), d(f) + d(f,j)} = min {¥; 13.7 +11} = 24.7;

d(t) = min {d(t), d(f) + d(f,t), d(b)+d(b,t)} = min {¥; 13.7 + 15, 6.2+8} = 14.2;

min {d(c), d(d), d(e), d(j), d(t)} = min {16; 20.9; ¥; 24.7; 14.2} = =14.2;

d(t) = 14.2.

Окрашиваем вершину t.

Вывод: Кратчайший путь из истока s в сток t только один,

состоит из дуг (s,b) и (b,t) и равен 14.2 единиц.

Рассмотренные положения по теории графов могут использоваться при решении задач моделирования объектов со сложной внутренней структурой. Алгоритмы, построенные с использованием теории графов, отличаются высоким быстродействием, а модели объектов и процессов получаются наглядными и простыми в программировании.

[AK1]