Дан ориентированный граф, состоящий из десяти вершин и ребер, соединяющих вершины между собой. Известен

Дан ориентированный граф, состоящий из десяти вершин и ребер, соединяющих вершины между собой. Известен вес каждого ребра. Требуется найти разрез графа и определить величину максимального потока от источника графа до стока. Вариант 3 10 4 7 5 9 1 6 8 2 3 10 12 8 3 2 12 6 10 5 3 4 8 6 15 10 11 2 10 4 7 5 9 1 6 8 2 3 10 12 8 3 2 12 6 10 5 3 4 8 6 15 10 11 2

10
4
7
5
9
1
6
8
2
3
10(0)
12(0)
8(0)
3(0)
2(0)
12(0)
6(0)
10(0)
5(0)
3(0)
4(0)
8(0)
6(0)
15(0)
10(0)
11(0)
2(0)
10
4
7
5
9
1
6
8
2
3
10(0)
12(0)
8(0)
3(0)
2(0)
12(0)
6(0)
10(0)
5(0)
3(0)
4(0)
8(0)
6(0)
15(0)
10(0)
11(0)
2(0)
Выбран путь:
x1→ x4 → x7→ x10
Вычисление пометок:
l(x1) = (+x1; ∞)
l(x4) = (+x1; min{σ(x1); q1 4 – ξ1 4}) = (+x1; min{∞; 8 – 0}) = (+x1; 8)
l(x7) = (+x4; min{σ(x4); q4 7 – ξ4 7}) = (+x4; min{8; 10 – 0}) = (+x4; 8)
l(x10) = (+x7; min{σ(x7); q7 10 – ξ7 10}) = (+x7; min{8; 15 – 0}) = (+x7; 8)
Переопределение потоков:
ξ7 10 = ξ7 10 + σ(x10) = 0 + 8 = 8
ξ4 7 = ξ4 7 + σ(x10) = 0 + 8 = 8
ξ1 4 = ξ1 4 + σ(x10) = 0 + 8 = 8
10
4
7
5
9
1
6
8
2
3
10(0)
12(0)
8(8)
3(0)
2(0)
12(0)
6(0)
10(8)
5(0)
3(0)
4(0)
8(0)
6(0)
15(8)
10(0)
11(0)
2(0)
10
4
7
5
9
1
6
8
2
3
10(0)
12(0)
8(8)
3(0)
2(0)
12(0)
6(0)
10(8)
5(0)
3(0)
4(0)
8(0)
6(0)
15(8)
10(0)
11(0)
2(0)
Выбран путь:
x1→ x2→ x5 → x8→ x10
Вычисление пометок:
l(x1) = (+x1; ∞)
l(x2) = (+x1; min{σ(x1); q1 2 – ξ1 2}) = (+x1; min{∞; 10 – 0}) = (+x1; 10)
l(x5) = (+x2; min{σ(x2); q2 5 – ξ2 5}) = (+x2; min{10; 2 – 0}) = (+x2; 2)
l(x8) = (+x5; min{σ(x5); q5 8 – ξ5 8}) = (+x5; min{2; 3 – 0}) = (+x5; 2)
l(x10) = (+x8; min{σ(x8); q8 10 – ξ8 10}) = (+x8; min{2; 10 – 0}) = (+x8; 2)
Переопределение потоков:
ξ8 10 = ξ8 10 + σ(x10) = 0 + 2 = 2
ξ5 8 = ξ5 8 + σ(x10) = 0 + 2 = 2
ξ2 5 = ξ2 5 + σ(x10) = 0 + 2 = 2
ξ1 2 = ξ1 2 + σ(x10) = 0 + 2 = 2
10
4
7
5
9
1
6
8
2
3
10(2)
12(0)
8(8)
3(0)
2(2)
12(0)
6(0)
10(8)
5(0)
3(2)
4(0)
8(0)
6(0)
15(8)
10(2)
11(0)
2(0)
10
4
7
5
9
1
6
8
2
3
10(2)
12(0)
8(8)
3(0)
2(2)
12(0)
6(0)
10(8)
5(0)
3(2)
4(0)
8(0)
6(0)
15(8)
10(2)
11(0)
2(0)
Выбран путь:
x1→ x3→ x6→ x7→ x10
Вычисление пометок:
l(x1) = (+x1; ∞)
l(x3) = (+x1; min{σ(x1); q1 3 – ξ1 3}) = (+x1; min{∞; 12 – 0}) = (+x1; 12)
l(x6) = (+x3; min{σ(x3); q3 6 – ξ3 6}) = (+x3; min{12; 12 – 0}) = (+x3; 12)
l(x7) = (+x6; min{σ(x6); q6 7 – ξ6 7}) = (+x6; min{12; 4 – 0}) = (+x6; 4)
l(x10) = (+x7; min{σ(x8); q7 10 – ξ7 10}) = (+x7; min{4; 15 – 8}) = (+x8; 4)
Переопределение потоков:
ξ7 10 = ξ7 10 + σ(x10) = 8 + 4 = 12
ξ6 7 = ξ6 7 + σ(x10) = 0 + 4 = 4
ξ3 6 = ξ3 6 + σ(x10) = 0 + 4 = 4
ξ1 3 = ξ1 3 + σ(x10) = 0 + 4 = 4
10
4
7
5
9
1
6
8
2
3
10(2)
12(4)
8(8)
3(0)
2(2)
12(4)
6(0)
10(8)
5(0)
3(2)
4(4)
8(0)
6(0)
15(12)
10(2)
11(0)
2(0)
10
4
7
5
9
1
6
8
2
3
10(2)
12(4)
8(8)
3(0)
2(2)
12(4)
6(0)
10(8)
5(0)
3(2)
4(4)
8(0)
6(0)
15(12)
10(2)
11(0)
2(0)
Выбран путь:
x1→ x2→ x4→ x5→ x7 → x10
Вычисление пометок:
l(x1) = (+x1; ∞)
l(x2) = (+x1; min{σ(x1); q1 2 – ξ1 2}) = (+x1; min{∞; 10 – 2}) = (+x1; 8)
l(x4) = (+x2; min{σ(x2); q2 4 – ξ2 4}) = (+x2; min{8; 3 – 0}) = (+x2; 3)
l(x5) = (+x4; min{σ(x4); q4 5 – ξ4 5}) = (+x4; min{3; 6 – 0}) = (+x4; 3)
l(x7) = (+x5; min{σ(x5); q5 7 – ξ5 7}) = (+x5; min{3; 5 – 0}) = (+x5; 3)
l(x10) = (+x7; min{σ(x7); q7 10 – ξ7 10}) = (+x7; min{3; 15 – 12}) = (+x7; 3)
Переопределение потоков:
ξ7 10 = ξ7 10 + σ(x10) = 12 + 3 = 15
ξ5 7 = ξ5 7 + σ(x10) = 0 + 3 = 3
ξ4 5 = ξ4 5 + σ(x10) = 0 + 3 = 3
ξ2 4 = ξ2 4 + σ(x10) = 0 + 3 = 3
ξ1 2 = ξ1 2 + σ(x10) = 2 + 3 = 5
10
4
7
5
9
1
6
8
2
3
10(5)
12(4)
8(8)
3(3)
2(2)
12(4)
6(3)
10(8)
5(3)
3(2)
4(4)
8(0)
6(0)
15(15)
10(2)
11(0)
2(0)
10
4
7
5
9
1
6
8
2
3
10(5)
12(4)
8(8)
3(3)
2(2)
12(4)
6(3)
10(8)
5(3)
3(2)
4(4)
8(0)
6(0)
15(15)
10(2)
11(0)
2(0)
Выбран путь:
x1→ x3→ x4→ x7→ x8 →x10
Вычисление пометок:
l(x1) = (+x1; ∞)
l(x3) = (+x1; min{σ(x1); q1 3 – ξ1 3}) = (+x1; min{∞; 12 – 4}) = (+x1; 8)
l(x4) = (+x3; min{σ(x3); q3 4 – ξ3 4}) = (+x3; min{8; 2 – 0}) = (+x3; 2)
l(x7) = (+x4; min{σ(x4); q4 7 – ξ4 7}) = (+x4; min{2; 10 – 8}) = (+x4; 2)
l(x8) = (+x7; min{σ(x7); q7 8 – ξ7 8}) = (+x7; min{2; 8 – 0}) = (+x7; 2)
l(x10) = (+x8; min{σ(x8); q8 10 – ξ8 10}) = (+x8; min{2; 10 – 2}) = (+x8; 2)
Переопределение потоков:
ξ8 10 = ξ8 10 + σ(x10) = 2 + 2 = 4
ξ7 8 = ξ7 8 + σ(x10) = 0 + 2 = 2
ξ4 7 = ξ4 7 + σ(x10) = 8 + 2 = 10
ξ3 4 = ξ3 4 + σ(x10) = 0 + 2 = 2
ξ1 3 = ξ1 3 + σ(x10) = 4 + 2 = 6
10
4
7
5
9
1
6
8
2
3
10(5)
12(6)
8(8)
3(3)
2(2)
12(4)
6(3)
10(10)
5(3)
3(2)
4(4)
8(2)
6(0)
15(15)
10(4)
11(0)
2(2)
10
4
7
5
9
1
6
8
2
3
10(5)
12(6)
8(8)
3(3)
2(2)
12(4)
6(3)
10(10)
5(3)
3(2)
4(4)
8(2)
6(0)
15(15)
10(4)
11(0)
2(2)
Вычисление пометок:
l(x1) = (+x1; ∞)
l(x2) = (+x1; min{σ(x1); q1 2 – ξ1 2}) = (+x1; min{∞; 10 – 5}) = (+x1; 5)
l(x3) = (+x1; min{σ(x1); q1 3 – ξ1 3}) = (+x1; min{∞; 12 – 6}) = (+x1; 6)
l(x6) = (+x3; min{σ(x3); q3 6 – ξ3 6}) = (+x3; min{6; 12 – 4}) = (+x3; 6)
Определение разреза:
10
4
7
5
9
1
6
8
2
3
10(5)
12(6)
8(8)
3(3)
2(2)
12(4)
6(3)
10(10)
5(3)
3(2)
4(4)
8(2)
6(0)
15(15)
10(4)
11(0)
2(2)
х0
х0
10
4
7
5
9
1
6
8
2
3
10(5)
12(6)
8(8)
3(3)
2(2)
12(4)
6(3)
10(10)
5(3)
3(2)
4(4)
8(2)
6(0)
15(15)
10(4)
11(0)
2(2)
х0
х0
(x0→ х0): (х1; x4), (x2; x4), (x2; x5), (x3; x4), (x6; x7)
Вычисление максимального потока:
ξmax = ∑(x0→ х0) qi j = 8+3+2+2+4 = 19
Ответ:
Разрез:
(x0→ х0): (х1; x4), (x2; x4), (x2; x5), (x3; x4), (x6; x7)
Максимальное значение потока:
ξmax = 19
Граф потоков:
10
4
7
5
9
1
6
8
2
3
5
6
8
3
2
4
3
10
3
2
4
2
15
4
2
10
4
7
5
9
1
6
8
2
3
5
6
8
3
2
4
3
10
3
2
4
2
15
4
2