Потоки. Сети

1.

Потоки. Сети.

2.

4
5
6
4
4
7
2
A
4
6
3
3
4
5
7
4
2
1
B

3.

Напомним некоторые понятия
теории графов.
• Узел орграфа s, полустепень захода indeg(s)
которого
равна
нулю
называется
источником.
S

4.

• Узел орграфа t, полустепень исхода
outdeg(t) которого равна нулю называется
стоком.
t

5.

• Сетью называется связанный орграф G(V,E)
с одним источником s и одним стоком t.
S
t

6.

• Разрезом графа G(V,E) называется такое
множество ребер P E, удаление которых
увеличивает
количество
компонент
связности.
s
(s,t)-разрез
t

7.

• Пусть G(V,E) – сеть, s – источник, а t – сток
сети.
Дуги
сети
нагружены
неотрицательными
вещественными
числами, c:E R. Если u и v – узлы сети, то
число c(u,v) – называется пропускной
способностью дуги .
c(u,v)
u
v

8.

• Пусть
задана
функция
f:E R.
Дивергенцией функции f в узле v
называется
число
div(f,v),
которое
определяется следующим образом:

9.

6
4
5
7
v
8
9
7

10.

• Функция f: E R называется потоком в
сети G, если
(u,v) E 0 f(u,v) c(u,v).
u V\{s,t}: div(f,u)=0.
• Число w(f)=div(f,s) называется величиной
потока f.

11.

• Дуга (u,v) называется насыщенной для
потока f, если f(u,v)=c(u,v).
3
6
5
4
8
8
3
6
4
3
2
7

12.

• Сумма пропускных способностей дуг
разреза
P
называется
пропускной
способностью разреза и обозначается C(P).
4
2
3
2
3
4

13.

• Сумма потоков через дуги разреза P
обозначается F(P)
2
2
3
3
4
4
3
2
3
2
4
4

14.

S
s
t
T

15.

16.

S
s

17.

s
S
T
t

18.

19.

20.

21.

22.

Пример
Для сети G(V,E) найти максимальный поток.
S
50
25
30
24
26
60
40
30
20
25
18
28
55
50
60
24
24
24
28
54
24
24
50
110
110
t
24

23.

Выберем произвольную аугментальную <s,t> цепь. Найдем наименьшую
пропускную способность дуги этой цепи, определим величины потоков
цепи равными этой величине.
S
50
25
25
60
30
40
50
60
30
20
25
25
24
26
25
18
28
55
24
24
54
24
24
25
24
28
50
110
110
t
24

24.

Выберем новую аугментальную <s,t> цепь, с учетом полученных величин
потока и найденной насыщенной дуги.
S
50
60
40
50
60
25+24
25
30
30
20
25
24
25
24
25
26
18
28
55
24
24
54
24
24
24
25+24
24
28
50
110
110
t
24

25.

S
50
25
24
40
30
20
30 28
24
55
25
18
24
28
24
24
54
24
25 +30
24
50
60
30
30
25
26
60
49
24
49 +30
50
110
110
t
24

26.

S
50
49
25
24
30
24
25
40
30
20
54
25
24
18
28
24
28
24
24
55
50
60
30+24
30
25
26
60
54
24
24
24
79+24
50
110
110
t
24

27.

S
50
49
25
40
24
30
24
25
54
30
20
25
24+4
18
28
54
4
24
24
24
103
24
28
24
24
55
50
60
54+4
30
25
26
60
4
50
110
110
t
24

28.

S
50
49
25
24
30
24
25
40
58
28
54
30
25
20
18
28
24
55
20
50
60
20
30
25
26
60
24
54
4+20
24
24 24
103
50
24
28
4+20
110
t
110
24

29.

S
50
49
25
60
24
30
24
50
60
20+18
58
20
30
25
40
28
20
18
30
25
18
28
24
28
24
26
25
24
55
54
54
24
24
24 24
18
103
50
24+18
110
t
110
24

30.

S
6
50
49
25
60
24
30
24
50
60
38
58
20
30
25
40
28
20
18
30
25
6
18
28
24
28
24
26
25
24
55
54
54
24
24 24
18+6
103
50
42+6
110
t
24
110
24

31.

S
6+24
50
49
25
60
24
30
24
50
60
38
58
20
30
25
40
28
20
30
18
6+24
18
28
25
24
55
54
24
24
24
24 24
24
103
50
48
110
110
24
t
24
28
24
26
25
54
24

32.

S
30+28
50
49
25
60
24
30
24
20
28
20
18
25
28
24
55
54
30
30
18
24
26
50
60
38
58
30
25
40
28
24
28
24
54
24
24
24 24
24
103
50
48
110
110
24+28
t
25
24
28

33.

S
58
50
49
25
60
24
30
24
60
38
58
20
30
25
40
28
20
18
18
28
24
26
25
24
55
54
25
50
30
28
30
24
24
28+25
24
50
24
54
24
103
25
28
24
24 24
25
48
110
110
52 +25
t

34.

S
58
50
49
25
60
24
30
24
20
28
20
18
25
24
55
54
25
30
25
28
24
53
24
24
24
103
50
48
110
110
77 +24
t
24
24
54
24
24 24
24
28
18
28
24
26
25 +24
50
60
38
58
30
25
40

35.

S
58
50
49
25
60
24
30
24
20
28
20
18
25
24
55
54
25
30
24
53
24
50
48
110
110
103
t
24
24
54
24
103
25
28
24
24 24
24
28
18
28
24
26
49
50
60
38
58
30
25
40
24

36.

Спасибо за внимание