Математическое программирование потоки в сетях

1.

МАТЕМАТИЧЕСКОЕ
ПРОГРАММИРОВАНИ
Е
ПОТОКИ В СЕТЯХ

2.

ПОТОКИ В СЕТЯХ
Цель: освоение навыков решения
задач построения потоков в сетях.
Задачи:
изучение основных понятий;
освоение навыков решения
задачи о максимальном потоке.

3.

План лекции
1. Основные понятия;
2. Постановка задачи о
максимальном потоке;
3. Решение задачи на основе
теоремы Форда-Фалкерсона;
4. Решение задачи на основе
алгоритма Форда-Фалкерсона.

4.

ПОТОКИ В СЕТЯХ
Основные понятия
G (V , E ) , каждому ребру
(vi , v j ) которого поставлено в соответствие число c(vi , v j ) 0 ,
называемое пропускной способностью, а также выделено две вершины v0 исток и vn 1 - сток, n V .
Поток – это функция f (vi , v j ) , (vi , v j ) E обладающая тремя
Сеть – это ориентированный граф
свойствами:
1. f (vi , v j ) c(vi , v j ) ;
2. f (vi , v j ) f (v j , vi ) (кососимметричность);
3.
f (u, v) 0 , u V {v0 , vn 1}
v V

5.

Величина потока f это
f f (v0 , v j )
v V
Примем vi V , f (vi , v j ) 0 , f (v j , vi ) 0
f (vi , v j ) - величина входящего потока для вершины v j
vi V
f (vi , v j ) - величина исходящего потока для вершины vi
v j V

6.

0
1
6
1
3
1
1
2
2
1
0 4
9
7
5
4
4
1
0
20
1
1
1
1
4
1
2
4
3
2
f f (v0 , v j ) 11 8 19
v V
15
5
7
8
4
4
1
3

7.

Разрез ( S , T ) сети G (V , E ) называется разбиение множества V
на две части S и
S T .
T такое, что
v0 S , vn 1 T , S T V ,
c( S , T ) – это сумма пропускных
способностей дуг соединяющих вершины в S и T .
Пропускная способность разреза
Минимальный разрез сети – это разрез с минимальной пропускной
способностью.

8.

0
1
6
1
3
1
1
2
2
1
0 4
9
7
20
5
4
4
1
4
3
Разрез ({0,1,4},{2,3,5})
c({0,1,4},{2,3,5})=c(1,2)+c(4,3)=12+14
=26

9.

1
0
1
1
1
1
2
2
4
7
8
15
5
4
4
1
1
3
Поток через разрез ({0,1,4},{2,3,5})
f(1,2)+f(4,3)+f(2,4)=12+11+(-4)=19

10.

Задача о максимальном потоке
Теорема Форда-Фалкерсона: В любой сети максимальная величина
потока из истока s в сток t равна минимальной пропускной
способности разреза отделяющего s от t .
0
1
6
1
3
1
1
2
2
1
0 4
9
7
20
5
4
4
1
4
3

11.

0
1
6
1
3
29
1
1
2
2
1
0 4
9
7
20
5
4
4
3
1
4
0
1
6
1
3
35
1
1
2
2
1
0 4
9
7
20
5
4
4
1
4
3

12.

0
1
6
1
3
58
1
1
2
2
1
0 4
9
7
20
5
4
4
3
1
4
0
1
6
1
3
52
1
1
2
2
1
0 4
9
7
20
5
4
4
1
4
3

13.

1
2
1
0
1
6
1
3
40
1
0 4
2
20
9
5
7
4
4
3
1
4
1
2
1
0
1
6
1
3
29
1
0 4
2
20
9
5
7
4
4
1
4
3

14.

1
0
1
6
1
3
53
1
0 4
2
1
2
20
9
5
7
4
4
1
4
0
3
1
1
6
1
3
46
1
0 4
1
2
2
20
9
5
7
4
4
1
4
3

15.

1
0
1
6
1
3
34
1
0 4
2
1
2
20
9
5
7
4
1
4
4
3
1
0
1
6
1
3
26
1
0 4
1
2
2
20
9
5
7
4
4
1
4
3

16.

1
0
1
6
1
3
4
2
1
2
1
0 4
20
9
5
7
4
1
4
4
3
1
0
1
6
1
3
27
1
0 4
1
2
2
20
9
5
7
4
4
1
4
3

17.

1
0
1
6
1
3
1
2
1
0 4
2
20
9
5
7
4
1
4
4
34
3
1
0
1
6
1
3
1
0 4
1
2
2
20
7
9
5
4
4
1
4
3
23

18.

1
0
1
6
1
3
40
2
1
2
1
0 4
20
9
5
7
4
1
4
4
3
1
0
1
6
1
3
24
1
0 4
1
2
2
20
9
5
7
4
4
1
4
3

19.

Понятие остаточной сети
Сеть G (V , E ) , c(vi , v j ) - пропускная способность дуги
12
1
2
16
20
10
0
5
9
4
7
13
4
4
3
14
Поток f (vi , v j )
12
1
2
11
15
0
5
4
1
7
8
4
4
11
3

20.

АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА
1. Обнуляем все потоки. Остаточная сеть изначально совпадает с
исходной сетью.
2. В остаточной сети находим любой путь из источника в сток. Если
такого пути нет, останавливаемся.
3. Пускаем через найденный путь (он называется увеличивающим
путём или увеличивающей цепью) максимально возможный поток:
На найденном пути в остаточной сети ищем ребро с
минимальной пропускной способностью cmin.
Для каждого ребра на найденном пути увеличиваем поток на
cmin, а в противоположном ему - уменьшаем на cmin.
Модифицируем остаточную сеть. Для всех рёбер на найденном
пути, а также для противоположных им рёбер, вычисляем новую
пропускную способность. Если она стала ненулевой, добавляем ребро к
остаточной сети, а если обнулилась, стираем его.
4. Возвращаемся на шаг 2.

21.

12
1
2
16
20
10
0
5
9
4
7
13
0
1
2
3
4
5
0
0
-4
0
0
0
0
4
4
14
1
4
0
-4
0
0
0
2
0
4
0
0
-4
0
3
3
0
0
0
0
4
-4
4
0
0
4
-4
0
0
5
0
0
0
4
0
0

22.

4
4
8
1
12
2
20
4
10
0
5
5
4
7
13
4
4
3
10
4
0
1
2
3
4
5
0
0
-11
0
0
0
0
1
11
0
-4
0
-7
0
2
0
4
0
7
-4
--7
3
0
0
-7
0
11
-4
4
0
7
4
-11
0
0
5
0
0
7
4
0
0

23.

4
11
8
1
5
13
4
3
7
2
0
5
5
7
11
13
4
4
3
3
11
0
1
2
3
4
5
0
0
-11
0
0
-8
0
1
11
0
-12
0
1
0
2
0
12
0
7
-4
-15
3
0
0
-7
0
11
-4
4
8
-1
4
-11
0
0
5
0
0
15
4
0
0

24.

-12
11
1
15
2
5
5
4
11
0
5
5
7
3
5
4
4
8
3
3
11
0
1
2
3
4
5
0
0
-11
0
0
-12
0
1
11
0
-12
0
1
0
2
0
12
0
7
-0
-19
3
0
0
-7
0
11
-4
4
12
-1
0
-11
0
0
5
0
0
19
4
0
0

25.

-12
11
1
19
2
5
1
11
0
5
9
7
3
1
4
4
12
3
3
11
0
1
2
3
4
5
0
0
-11
0
0
-12
0
1
11
0
-12
0
1
0
2
0
12
0
7
-0
-19
3
0
0
-7
0
11
-4
4
12
-1
0
-11
0
0
5
0
0
19
4
0
0

26.

0
0
-11
0
0
-12
0
0
1
2
3
4
5
1
11
0
-12
0
1
0
1
2
0
12
0
7
-0
-19
12
3
0
0
-7
0
11
-4
4
12
-1
0
-11
0
0
2
11
0
5
0
0
19
4
0
0
19
5
1
7
12
4
4
11
3