Дискретная математика
.pdfДля всех вершин транспортной сети свойства потока выполнены.
13.Помещаем вершины, в которые есть путь из источника, во множество вершин V1 (рассматриваем исходную транспортную сеть G).
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
|
|
|
4 @s |
@ |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
v1 - |
|
|
|
|
-3 |
|
|
|
|||||
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
3 |
@s-5 |
@ |
|
|
|
||||||||
|
|
|
|
@@ v4 |
|
|
@@ |
|
|
|
||||
v0 |
si@-- |
|
s |
|
- |
s |
v6 |
|||||||
|
- |
3 |
|
|
@ |
|
5 |
@ |
|
|
||||
|
2 |
- |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||||
|
@ |
2 |
|
|
|
|
||||||||
|
@ |
|
|
|
|
|
|
|
|
|
||||
|
|
@ |
|
|
|
|
|
|
||||||
|
v2s@- |
- |
6 |
|
|
|
||||||||
|
|
@ |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
1@@s |
|
|
|
|
|||||
|
|
|
|
G |
|
v5 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Так как все дуги, смежные с источником, насыщенны, то ни в одну вершину, за исключением самого источника, пути нет.
V1 = {v0},
V2 = {v1, v2, v3, v4, v5, v6}. Вершину v пометим символом i;0 вершины, принадлежащие множеству V2 - символом .
14.Минимальный разрез содержит ребра, соединяющие вершины, принадлежащие разным подмножествам. В нашем примере это 3 ребра:
E1 = {((v0, v1), 3), ((v0, v4), 3), ((v0, v2), 2)}.
∑
(E1) = c(v0, v1) + c(v0, v4) + c(v0, v2) = 3 + 3 + 2 = 8;
∑
(E1) = 8 = |φ|.
Мы убедились, что пропускная способность разреза равна величине максимального потока.
Замечание 13.4. Поскольку пути из источника в сток выбираются произвольным образом, при другом выборе пути можно получить другое решение, другой итоговый поток и минимальный разрез. Тем не менее, величина максимального потока и пропускная способность разреза будут одинаковы (в нашем случае равны 8).
Пример 13.4. Найти максимальный поток в транспортной сети G.
251
|
v1 |
|
|
|
|
|
|
|
v3 |
|
|
|||
6 |
|
@s-3-3 |
|
|
2 |
@s- |
|
|||||||
|
|
|
@@ |
|
|
|
|
@@ |
|
|||||
- |
|
|
|
|
|
- |
|
|
|
6 |
@ |
|||
|
|
|
|
|
|
@ |
|
|
|
|
|
|||
v0 s@- |
|
|
|
|
@ |
|
|
- |
|
sv5 |
||||
5 |
|
|
|
|
|
|
|
@ |
4 |
|||||
@ |
v2s |
|
|
|
|
vs4 |
||||||||
|
|
-4 |
|
|
@ |
|
|
|||||||
|
@ |
|
|
|
|
|
|
|
|
|
|
|||
|
|
@ |
|
|
|
|
|
|
|
|
@ |
|
|
|
G
Решение.
1.Источником в данной транспортной сети является вершина v0, а стоком - вершина v5.
2.Строим граф перестроек G′1, включая в него все вершины исходной транспортной сети G и заменяя каждую дугу на две;
|φ| = 0.
3.
|
v1 |
|
- |
v3 |
|
|
||
- |
6 |
s0 |
0 |
3 |
s0- |
|
||
|
|
|
|
- |
|
sv5 |
||
0 |
|
|
|
3 |
|
6 |
||
|
|
|
-2 |
|
|
|||
v0 s0- |
|
- |
4 |
|||||
|
|
|
- |
|
|
|||
|
|
vs4 |
|
|||||
|
v2s |
|
0 |
4 |
|
|
||
|
5 |
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
||
4. |
|
|
|
|
G1′ |
|
|
|
|
s0 |
|
0 |
s3- |
|
|||
|
3 |
3 |
|
|||||
|
v1 |
|
- |
v3 |
|
|
||
- |
|
|
|
|
- |
|
sv5 |
|
3 |
|
|
|
3 |
|
3 |
||
|
|
|
-2 |
|
|
|||
v0 s0- |
|
- |
4 |
|||||
|
|
|
- |
|
|
|||
|
|
vs4 |
|
|||||
|
v2s |
|
0 |
4 |
|
|
||
|
5 |
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
G′2
5.
Путь L1:
6 |
3 |
6 |
v0 7→v1 |
7→v3 7→v5. |
|
Поток |
φ, |
прошедший |
по дугам этого пути, равен
φ = min( 6, 3, 6) = 3; |φ| = 0 + 3 = 3.
Путь L2:
5 |
4 |
4 |
; |
v0 7→v2 |
7→v4 |
7→v5 |
φ = min( 5, 4, 4) = 4; |φ| = 3 + 4 = 7.
252
v0
6.
|
3 |
s0 |
3 0 |
s3- |
||
|
v1 |
|
- |
v3 |
|
|
- |
|
|
|
- |
|
|
|
|
|
||||
s4- |
|
-2 |
|
0 |
||
3 |
|
|
|
3 |
|
3 |
|
|
|
- |
- |
|
|
|
|
vs4 |
||||
|
v2s |
|
4 0 |
|
||
|
1 |
|
0 |
|
4 |
|
|
|
|
|
|
G′3
sv5
Путь L3:
1 |
2 |
3 |
; |
v0 7→v2 |
7→v3 |
7→v5 |
φ = min( 1, 2, 3) = 1; |φ| = 7 + 1 = 8.
|
|
v1 |
|
- |
v3 |
|
|
|
|
|
|
|
3 |
s0 |
3 0 |
s4- |
s |
Путь L4: |
4 |
1 2 |
|
|
s5- |
|
|
-1 |
0 |
3 |
||||
v0 |
- |
|
|
|
- |
v5 |
3 |
4 |
||
3 |
|
|
v0 7→v1 |
7→v4 |
7→ |
|||||
|
|
|
|
|
3 |
2 |
|
|
|
|
|
0 |
|
|
- |
- |
|
|
7→v2 7→v3 7→v5. |
||
|
|
v2s |
1 |
4 0 |
vs4 |
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
G′4
Путь содержит дугу (v4, v2). Пропускная способность дуги (v2, v4) в исходной транспортной сети равна 4. При вычислении потока, проходящего по пути L4, учитываем реверсную способность дуги, так как именно ребро l′′ (то есть, ребро, направленное в сторону, противоположную дуге (v2, v4)), направлено параллельно этому пути.
|
|
φ = min( 3, 3, 4, 1, 2) = 1; |φ| = 8 + 1 = 9. |
|
|||||||||||||
7. |
|
|
|
|
|
|
|
|
|
|
|
Все дуги, сонаправленные |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
- |
|
|
|
|
пути, |
уменьшают |
про- |
|||||
|
v1 |
|
|
v3 |
|
|
пускные |
способности |
(в |
|||||||
|
|
s1 |
3 |
|
|
|
|
s5- |
|
том числе и |
дуга |
(v4, v2): |
||||
- |
2 |
0 |
|
|||||||||||||
|
|
|
|
c(v4, v2) = 4 − 1 = 3); |
||||||||||||
|
|
|
2- |
1 |
|
|||||||||||
4 |
|
|
|
|
|
|
|
|
- |
|
|
все |
ориентированные |
|||
v0 s5- |
|
|
-2 |
0 |
sv5 |
ребра, |
направленные |
в |
||||||||
|
|
0 |
- |
|
4 |
|
противоположную |
пути |
||||||||
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v2s |
|
3 |
|
|
1 |
vs4 |
|
|
сторону, |
|
увеличивают |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
G5′ |
|
|
|
пропускные |
способности |
(c(v2, v4) = 0 + 1 = 1).
8. Больше пути по дугам с ненулевыми пропускными способностями
253
нет. Строим итоговый поток. |
|
|
|
|
|
|
|||||||||||||||||||
|
v1 |
|
|
|
|
|
|
|
|
v3 |
|
|
Проверяем, выполнены ли |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
4 |
|
@s-1-3 |
|
|
2 |
@s- |
свойства |
потока |
|
во всех |
|||||||||||||||
|
|
|
|
@ |
@ |
|
|
|
|
|
@ |
@ |
вершинах: |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a) поток, исходящий из ис- |
|||||||||||
- |
|
|
|
|
|
@- |
|
|
5 |
@ |
|||||||||||||||
v0 s@- |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
sv5 |
точника 4 + 5 = |
| |
φ |
| |
= 9; |
||||
@@ @@ 4 |
|
|
|
|
|||||||||||||||||||||
5 |
|
|
|
- |
|
|
|
|
|
- |
|
|
б) поток, входящий в сток |
||||||||||||
|
|
@ |
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
||||||||
|
v2 |
s |
|
3 |
|
|
|
|
v |
s4 |
|
|
5 + 4 = |φ| = 9; |
||||||||||||
|
|
|
|
G |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в) поток в промежуточных вершинах |
|
|
|
|
|
||||||||||||||||||||
v1 : 4 = 3 + 1; |
|
|
|
|
|
|
|
v2 : 5 = 2 + 3; |
v3 : 3 + 2 = 5; |
||||||||||||||||
v4 : |
1 + 3 = 4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Во всех вершинах свойства потока выполняются. |
|
|
|
i верши- |
|||||||||||||||||||||
9. Находим минимальный разрез, |
помечая символом |
|
|||||||||||||||||||||||
ны, в которые существует путь из источника (множество V1). |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Несмотря на то, что дуга |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(v0, v2) насыщенна, в вер- |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
шину v2 |
можно |
|
попасть |
||
6 |
|
@si-3-3 |
|
2 |
@s- |
по ненасыщенным |
|
дугам |
|||||||||||||||||
|
|
(v0, v1), (v1, v4) и (v4, v2). |
|||||||||||||||||||||||
|
v1 |
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|||||||
- |
|
|
|
|
|
- |
|
|
|
6 |
|
Вершина |
v2 принадлежит |
||||||||||||
|
|
|
|
@ |
@ |
|
|
|
|
|
@ |
@ |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
множеству V1. |
|
|
|
|
|||||||
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
||||
v0 si@- |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
sv5 |
|
|
|
|
|||||
@ |
|
|
|
|
|
|
|
@ |
|
vsi4 |
4 |
Дуги (v1, v3), (v2, v3) и |
|||||||||||||
|
v2si |
|
-4 |
|
|
|
|
|
|
вершинам |
v3 и |
|
v5 пути |
||||||||||||
|
@ |
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
(v4, v5) - |
насыщенны, к |
||||
5 |
|
|
|
|
|
|
|
|
|
|
- |
|
|
||||||||||||
|
|
@ |
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
G |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
из источника по дугам с |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ненулевыми пропускными |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
способностями нет. |
|
|
|||
|
|
|
|
|
V1 = {v0, v1, v2, v4}; |
V2 = {v3, v5}. |
|
|
|
|
Минимальный разрез включает 3 ребра:
E1 = {(v1, v3), (v2, v3), (v4, v5)}.
Проверим выполнение теоремы Форда-Фалкерсона:
(E1) = c(v1, v3) + c(v2, v3) + c(v4, v5) = 3 + 2 + 4 = 9 = |φ|.
254
Пример 13.5. Найти максимальный поток в транспортной сети, заданной списком дуг
{((v0, v1), 22) , ((v0, v4), 8) , ((v0, v2), 23) , ((v1, v3), 8) , ((v1, v6), 6) , ((v1, v4), 10) , ((v2, v4), 10) , ((v2, v7), 10) , ((v2, v5), 8) , ((v3, v6), 10) , ((v4, v6), 7) , ((v4, v8), 10) , ((v4, v7), 7) , ((v5, v7), 5) , ((v6, v8), 18) , ((v7, v8), 24)}.
Решение.
1.Изобразим транспортную сеть, заданную списком дуг, графически:
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
8 |
|
@s-10 |
|
|
|
|
|
|
||||||||
|
|
|
v1 |
|
|
|
|
6 |
|
@@ |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
- |
|
|
|
|
@ |
v |
|
|
|
||||||
22 |
|
@s-10 |
|
|
|
|
|
@s-618 |
|
|
||||||||||||||
|
|
|
|
|
|
@ |
@ |
|
|
|
|
|
7 |
|
|
@ |
@ |
|
|
|||||
|
|
|
8 |
|
|
|
|
|
|
|
|
10 |
|
|
|
|||||||||
- |
|
|
|
|
|
|
|
|
- |
|
|
|
|
|
||||||||||
v0 |
|
|
- |
|
|
|
|
|
|
@ |
|
- |
|
|
|
|
@ |
v8 |
||||||
s@- |
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
10 vs4-7 |
- |
|
|
s |
||||||||||||||||
23 |
|
- |
|
|
|
10 |
@ |
|
|
|
|
|
|
|||||||||||
@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
@ |
@ |
|
|
|
|
|
|
|
|
@ |
@ |
24 |
||||||||||
|
|
|
v2 |
s@-8- |
|
|
|
|
|
sv7 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
@ |
|
|
|
- |
5 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
@ |
@s |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v5
G
2. Строим граф перестроек G′1; |φ| = 0.
v0
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
8 |
|
s0- |
|
|
|||||
|
|
- 10 |
|
|
|
||||||||
|
v1 |
0 |
|
v |
|
||||||||
|
|
|
|
|
|
|
|
6 |
|
|
|
||
|
|
|
s0-0 |
|
|
|
|
s0-6 |
|||||
- |
22 |
|
|
7 |
|
||||||||
- 10 |
- |
- 18 |
|||||||||||
0 |
|
|
0 |
||||||||||
|
|
8 |
|
|
|
|
|
|
10 24 |
||||
s0-0 |
10 vs40-0 |
||||||||||||
23 |
- |
- |
- |
|
|||||||||
|
|
|
0 |
|
|
|
10 |
7 |
|
0 |
|
||
|
v2s0-0 |
5 |
|
sv7 |
|||||||||
|
|
|
|
- |
|
|
|
|
|||||
|
|
|
|
s |
|
|
|
|
|||||
|
|
|
|
|
8 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G′1 v5
sv8
L1 :
22 |
8 |
10 |
18 |
; |
v0 7→v1 |
7→v3 |
7→v6 |
7→v8 |
φ = min(22, 8, 10, 18);φ = 8;
|φ| = 0 + 8 = 8.
255
3.Изменяем пропускные способности дуг, вошедших в путь L1. Получаем новый граф перестроек G′2.
v0
4.
v0
5.
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
0 |
|
s8- |
|
|
|
||||
|
|
- |
|
|
|
|
|||||||
|
v1 |
|
|
|
|
|
|||||||
|
|
|
8 |
|
|
|
|
6 |
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
s0-0 |
|
|
|
s8-6 |
||||||
- |
14 |
|
|
7 |
|
||||||||
- 10 |
- |
- 10 |
|||||||||||
8 |
|
0 |
|||||||||||
|
|
8 |
|
|
|
|
|
10 |
|
||||
s0-0 |
10 vs40-0 |
24 |
|||||||||||
23 |
- |
- |
- |
|
|||||||||
|
|
|
0 |
|
|
|
10 |
7 |
|
0 |
|
|
|
|
v2s0-0 |
5 |
|
sv7 |
|
||||||||
|
|
|
|
- |
|
|
|
|
|
||||
|
|
|
|
|
vs5 |
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G2′ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
0 |
|
s8- |
|
|
|
||||
|
|
- |
|
|
|
|
|||||||
|
v1 |
|
|
|
|
|
|||||||
|
|
|
8 |
|
|
|
|
0 |
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
s0-6 |
|
|
|
14s -6 |
||||||
- |
8 |
|
|
7 |
|
||||||||
- 10 |
- |
- |
|||||||||||
14 |
|
|
8 |
|
|
0 |
|
|
|
10 |
4 |
||
s0-0 |
10 vs40-0 |
24 |
|||||||||||
23 |
- |
- |
- |
|
|||||||||
|
|
|
0 |
|
|
|
10 |
7 |
|
0 |
|
|
|
|
v2s0-0 |
5 |
|
sv7 |
|
||||||||
|
|
|
|
- |
|
|
|
|
|
||||
|
|
|
|
|
vs5 |
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G′3
sv8
sv8
14 |
6 |
10 |
; |
L2 : v0 7→v1 |
7→v6 |
7→v8 |
φ = min( 14, 6, 10) = 6; |φ| = 8 + 6 = 14.
L3 :
8 |
10 |
7 |
4 |
; |
v0 7→v1 |
7→v4 |
7→v6 |
7→v8 |
φ = min( 8, 10, 7, 4) = 4; |φ| = 14 + 4 = 18.
256
v0
6.
v0
7.
v0
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
0 |
|
s8- |
|
|
|
||||
|
|
- |
|
|
|
|
|||||||
|
v1 |
|
|
|
|
|
|||||||
|
|
|
8 |
|
|
|
|
0 |
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
s4-6 |
|
|
|
18s -6 |
||||||
- |
4 |
|
|
3 |
|
||||||||
- |
- |
- |
|||||||||||
18 |
|
|
8 |
6 |
|
4 |
|
|
|
10 |
0 |
||
s0-0 |
10 vs40-0 |
24 |
|||||||||||
23 |
- |
- |
- |
|
|||||||||
|
|
|
0 |
|
|
|
10 |
7 |
|
0 |
|
|
|
|
v2s0-0 |
5 |
|
sv7 |
|
||||||||
|
|
|
|
- |
|
|
|
|
|
||||
|
|
|
|
|
vs5 |
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G4′ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
0 |
|
s8- |
|
|
|
||||
|
|
- |
|
|
|
|
|||||||
|
v1 |
|
|
|
|
|
|||||||
|
|
|
8 |
|
|
|
|
0 |
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
s4-6 |
|
|
|
18s -6 |
||||||
- |
4 |
|
|
3 |
|
||||||||
- |
- |
- |
|||||||||||
18 |
|
|
0 |
6 |
|
4 |
|
|
|
2 |
0 |
||
s0-8 |
10 vs40-8 |
24 |
|||||||||||
23 |
- |
- |
- |
|
|||||||||
|
|
|
0 |
|
|
|
10 |
7 |
|
0 |
|
|
|
|
v2s0-0 |
5 |
|
sv7 |
|
||||||||
|
|
|
|
- |
|
|
|
|
|
||||
|
|
|
|
|
vs5 |
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G5′ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
0 |
|
s8- |
|
|
|
||||
|
|
- |
|
|
|
|
|||||||
|
v1 |
|
|
|
|
|
|||||||
|
|
|
8 |
|
|
|
|
0 |
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
s4-6 |
|
|
|
18s -6 |
||||||
- |
4 |
|
|
3 |
|
||||||||
- |
- |
- |
|||||||||||
18 |
|
|
0 |
6 |
|
4 |
|
|
|
2 |
0 |
||
10s -8 |
10 vs40-8 |
14 |
|||||||||||
13 |
- |
- |
- |
|
|||||||||
|
|
|
0 |
|
|
|
0 |
7 |
|
10 |
|
|
|
|
v2s0-10 |
5 |
|
sv7 |
|
||||||||
|
|
|
|
- |
|
|
|
|
|
||||
|
|
|
|
|
vs5 |
|
|
|
|
|
|
||
|
|
|
|
|
8 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G′6
sv8
sv8
sv8
8 |
10 |
; |
L4 : v0 7→v4 |
7→v8 |
φ = min( 8, 10) = 8; |φ| = 18 + 8 = 26.
23 |
10 |
24 |
; |
L5 : v0 7→v2 |
7→v7 |
7→v8 |
φ = min(23, 10, 24) = 10; |φ| = 26 + 10 = 36.
L6 :
13 8 5 14
v0 7→v2 7→v5 7→v7 7→v8;
φ = min(13, 8, 5, 14) = 5; |φ| = 36 + 5 = 41.
257
8.
v0
9.
v0
10.
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
0 |
|
s8- |
|
|
|
||||
|
|
- |
|
|
|
|
|||||||
|
v1 |
|
|
|
|
|
|||||||
|
|
|
8 |
|
|
|
|
0 |
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
s4-6 |
|
|
|
18s -6 |
||||||
- |
4 |
|
|
3 |
|
||||||||
- |
- |
- |
|||||||||||
18 |
|
|
0 |
6 |
|
4 |
|
|
|
2 |
0 |
||
15s -8 |
10 vs40-8 |
9 |
|||||||||||
|
- |
- |
- |
|
|||||||||
|
8 |
|
0 |
|
|
|
0 |
7 |
|
15 |
|
|
|
|
v2s5-10 |
0 |
|
sv7 |
|
||||||||
|
|
|
|
- |
|
|
|
|
|
||||
|
|
|
|
|
vs5 |
|
|
|
|
|
|
||
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G7′ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
||
|
|
- |
|
0 |
|
s8- |
|
|
|
||||
|
|
- |
|
|
|
|
|||||||
|
v1 |
|
|
|
|
|
|||||||
|
|
|
8 |
|
|
|
|
0 |
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
s4-6 |
|
|
|
18s -6 |
||||||
- |
4 |
|
|
3 |
|
||||||||
- |
- |
- |
|||||||||||
18 |
|
|
0 |
6 |
|
4 |
|
|
|
0 |
0 |
||
17s -8 |
8 vs40-10 |
9 |
|||||||||||
|
- |
- |
- |
|
|||||||||
|
6 |
|
2 |
|
|
|
0 |
7 |
|
15 |
|
|
|
|
v2s5-10 |
0 |
|
sv7 |
|
||||||||
|
|
|
|
- |
|
|
|
|
|
||||
|
|
|
|
|
vs5 |
|
|
|
|
|
|
||
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G′8
sv8
sv8
8 |
10 |
2 |
; |
L7 : v0 7→v2 |
7→v4 |
7→v8 |
φ = min( 8, 10, 2) = 2; |φ| = 41 + 2 = 43.
L8 :
6 8 7 9
v0 7→v2 7→v4 7→v7 7→v8;
φ = min( 6, 8, 7, 9) = 6; |φ| = 43 + 6 = 49.
258
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
- |
|
0 |
|
s8- |
|
|
|
|
|
|||||
|
|
|
|
|
- |
|
|
|
|
|
|
||||||||
|
|
|
|
v1 |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
8 |
|
|
|
|
0 |
|
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
s4-6 |
|
|
|
|
18s -6 |
|
||||||||
|
- |
|
4 |
|
3 |
|
|
||||||||||||
|
- |
- |
- |
sv8 |
|||||||||||||||
|
18 |
|
|
|
|
0 |
6 |
|
4 |
|
|
|
|
0 |
0 |
||||
v0 |
23s -8 |
2 vs46-10 |
3 |
||||||||||||||||
|
|
- |
- |
- |
|
|
|||||||||||||
|
|
|
|
s |
|
|
|||||||||||||
|
|
|
0 |
|
8 |
|
|
|
0 |
1 |
|
21 |
|
|
|
||||
|
|
|
|
v2s5-10 |
0 |
|
v7 |
|
|
||||||||||
|
|
|
|
|
|
|
- |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
vs5 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11. |
|
|
|
|
|
G9′ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
- |
|
0 |
|
s8- |
|
|
|
|
|
|||||
|
|
|
|
|
- |
|
|
|
|
|
|
||||||||
|
|
|
|
v1 |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
8 |
|
|
|
|
0 |
|
2 |
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
s5-6 |
|
|
|
|
18s -6 |
|
||||||||
|
- |
|
3 |
|
3 |
|
|
||||||||||||
|
- |
- |
- |
sv8 |
|||||||||||||||
|
19 |
|
|
|
|
0 |
5 |
|
4 |
|
|
|
|
0 |
0 |
||||
v0 |
23s -8 |
2 vs47-10 |
2 |
||||||||||||||||
|
|
- |
- |
- |
|
|
|||||||||||||
|
|
|
|
s |
|
|
|||||||||||||
|
|
|
0 |
|
8 |
|
|
|
0 |
0 |
|
22 |
|
|
|
||||
|
|
|
|
v2s5-10 |
0 |
|
v7 |
|
|
||||||||||
|
|
|
|
|
|
|
- |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
vs5 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12. |
|
|
|
|
G10′ |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
8 |
@s-8 |
|
|
|
|
|
|
|||||
|
|
|
|
v1 |
|
|
@@ |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
- |
|
|
6 |
|
|
@ v |
|
|
|
||||
|
|
|
|
|
|
|
- |
|
|
|
|
|
|||||||
|
19 |
|
@s-5 |
|
|
|
|
@s-618 |
|
||||||||||
|
|
|
|
@ |
|
|
|
4 |
|
|
@ |
|
|
||||||
|
|
|
|
8 |
@ |
|
|
10 |
|
@ |
|
||||||||
|
- |
|
|
|
|
|
|
- |
|
|
|
@ v8 |
|||||||
v0 |
|
- |
|
@ |
|
|
- |
|
|
||||||||||
|
s@- |
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
s |
|||
|
|
- |
8 vs4-7 |
|
- |
|
|||||||||||||
|
23 |
|
|
|
10 |
|
|
|
|
|
|||||||||
|
@ |
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|||||
|
|
@ |
|
|
|
|
|
|
@ |
|
|
|
22 |
|
|||||
|
|
|
|
@ |
|
|
|
|
|
|
@ |
|
|
|
|||||
|
|
|
|
v2s@-5- |
|
|
sv7 |
|
|
|
|||||||||
|
|
|
|
|
|
@ |
|
|
- |
5 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
@s |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
v5
G
L9 :
4 |
6 |
1 |
3 |
; |
v0 7→v1 |
7→v4 |
7→v7 |
7→v8 |
φ = min( 4, 6, 1, 3) = 1; |φ| = 49 + 1 = 50.
Больше пути из источника в сток по дугам с ненулевой пропускной способностью нет. Строим итоговый поток.
Проверим, выполняются ли свойства потока:
a) в источнике
∑
φ(l) = 19 + 8 + 23 =
l M+(v0)
= 50 = |φ|
б)в стоке
∑
φ(l) = 18 + 8 + 22 =
l M−(v8)
= 50 = |φ|
259
в) во всех промежуточных вершинах |
|
|
|
||||||
v1 : |
|
|
φ(l) = 19 = 8 + 6 + 5 = |
|
|
|
φ(l); |
||
|
l M−(v1) |
|
|
l M |
+(v1) |
|
|||
v2 : |
|
∑ |
φ(l) = 23 = 8 + 10 + 5 = |
∑ |
φ(l); |
||||
|
|
∑ |
|
|
|
|
|
∑ |
|
|
l M−(v2) |
|
∑ |
l M+(v2) |
|||||
v3 : |
|
∑ |
|
|
|
|
|
||
|
|
φ(l) = 8 = 8 = |
|
φ(l); |
|
|
|||
|
l M−(v3) |
l M+(v3) |
|
|
|
|
|
||
v4 : |
|
|
φ(l) = 5 + 8 + 8 = 4 + 10 + 7 = |
φ(l); |
|||||
|
l M−(v4) |
|
|
|
|
|
|
l M+(v4) |
|
v5 : |
|
∑ |
φ(l) = 5 = 5 = |
∑ |
φ(l); |
|
∑ |
||
|
|
∑ |
|
|
|
|
|
|
|
|
l M−(v5) |
l M+(v5) |
|
|
|
|
φ(l); |
||
v6 : |
|
|
φ(l) = 8 + 6 + 4 = 18 = |
|
|
|
|||
|
l M−(v6) |
|
|
l M |
+(v6) |
|
|||
v7 : |
|
∑ |
φ(l) = 7 + 10 + 5 = 22 = |
∑ |
φ(l). |
||||
|
|
∑ |
|
|
|
|
|
∑ |
|
|
l M−(v7) |
|
|
l |
M+(v7) |
13.Находим минимальный разрез, отмечая символом iвершины, принадлежащие множеству V1 и символом - вершины, принадлежащие множеству V2.
|
|
|
|
|
|
|
|
8 |
@si-10 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
v1 |
|
|
@@ |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
- |
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
||||
22 |
@si-10 |
|
|
|
@si-618 |
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
- |
|
|
@ v |
|
|
|
|
||||||||
|
|
|
|
|
|
|
@ |
|
|
|
|
|
7 |
|
|
|
|
@ |
|
|
s |
||
|
si@- |
|
|
|
10 |
vsi4-7 |
|
|
|
|
|
@ |
|
||||||||||
|
|
|
|
8 |
|
|
|
@ |
|
|
|
|
10 |
|
|
|
|
||||||
- |
|
|
|
|
|
|
- |
|
|
|
|
|
|||||||||||
v0 |
|
|
- |
|
|
|
|
|
@ |
- |
|
|
|
|
|
@ |
|
v8 |
|||||
|
23 |
- |
|
|
|
@ |
|
- |
|
|
|||||||||||||
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
10 |
|
|
|
|
|||||||||||||||
|
|
@ |
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
||||
|
|
|
@ |
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
24 |
|||||
|
|
|
v2si@-8- |
s |
|
v7 |
|
|
|
|
|||||||||||||
|
|
|
|
@ |
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
@ |
|
|
- |
5 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
@ |
@si |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
G |
|
|
|
v5 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В вершину v1 можно попасть из источника по ненасыщенной дуге (v0, v1), из вершины v1 - в вершины v4 и v6. В вершину v3 можно добраться из v6 по дуге (v6, v3) с пропускной способностью 2.
Аналогично, в вершину v2 есть путь из источника по дугам (v0, v4) и (v4, v2), из вершины v2 есть путь в вершину v5.
Эти вершины образуют множество V1:
V1 = {v0, v1, v2, v3, v4, v5, v6 }.
Две оставшиеся вершины включаем во множество V2:
V2 = {v7, v8 }.
260