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