Математическая экономика
.pdf№ 1-17
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
5 |
9 |
2 |
6 |
|
|
|
|
|
x2 |
|
11 |
|
|
|
|
|
7 |
|
x3 |
|
|
17 |
|
|
|
|
2 |
|
x4 |
|
|
|
2 |
3 |
|
4 |
|
|
x5 |
|
|
|
|
|
6 |
|
|
|
x6 |
|
|
|
|
|
1 |
9 |
7 |
5 |
x7 |
|
|
|
|
|
|
|
|
8 |
x8 |
|
|
|
|
|
|
|
2 |
6 |
x9 |
|
|
|
|
|
|
|
|
4 |
x10 |
|
|
Исток: x5 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
№ 1-19 |
|
|
|
|
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
1 |
9 |
6 |
3 |
|
|
|
|
|
x2 |
|
5 |
|
|
|
|
|
7 |
|
x3 |
|
|
9 |
|
|
|
|
2 |
|
x4 |
|
|
|
4 |
7 |
|
5 |
|
|
x5 |
|
|
|
|
|
10 |
|
|
|
x6 |
|
|
|
|
|
7 |
8 |
2 |
4 |
x7 |
|
|
|
|
|
|
|
|
8 |
x8 |
|
|
|
|
|
|
|
4 |
3 |
x9 |
|
|
|
|
|
|
|
|
6 |
x10 |
|
|
Исток: x1 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
№ 1-21 |
|
|
|
|
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
7 |
1 |
1 |
5 |
|
|
|
|
|
x2 |
|
7 |
|
|
|
|
|
6 |
|
x3 |
|
|
2 |
|
|
|
|
3 |
|
x4 |
|
|
|
6 |
8 |
|
11 |
|
|
x5 |
|
|
|
|
|
14 |
|
|
|
x6 |
|
|
|
|
|
6 |
1 |
5 |
8 |
x7 |
|
|
|
|
|
|
|
|
4 |
x8 |
|
|
|
|
|
|
|
5 |
1 |
x9 |
|
|
|
|
|
|
|
|
7 |
x10 |
|
|
Исток: x2 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
№ 1-18
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
5 |
13 |
9 |
4 |
|
|
|
|
|
x2 |
|
6 |
|
|
|
|
|
11 |
|
x3 |
|
|
2 |
|
|
|
|
7 |
|
x4 |
|
|
|
8 |
7 |
|
4 |
|
|
x5 |
|
|
|
|
|
2 |
|
|
|
x6 |
|
|
|
|
|
5 |
5 |
2 |
1 |
x7 |
|
|
|
|
|
|
|
|
9 |
x8 |
|
|
|
|
|
|
|
4 |
7 |
x9 |
|
|
|
|
|
|
|
|
3 |
x10 |
|
|
Исток: x9 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
№ 1-20 |
|
|
|
|
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
9 |
6 |
2 |
3 |
|
|
|
|
|
x2 |
|
1 |
|
|
|
|
|
5 |
|
x3 |
|
|
3 |
|
|
|
|
5 |
|
x4 |
|
|
|
8 |
4 |
|
1 |
|
|
x5 |
|
|
|
|
|
6 |
|
|
|
x6 |
|
|
|
|
|
1 |
5 |
7 |
2 |
x7 |
|
|
|
|
|
|
|
|
9 |
x8 |
|
|
|
|
|
|
|
3 |
4 |
x9 |
|
|
|
|
|
|
|
|
5 |
x10 |
|
|
Исток: x10 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
№ 1-22 |
|
|
|
|
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
4 |
2 |
9 |
5 |
|
|
|
|
|
x2 |
|
2 |
|
|
|
|
|
4 |
|
x3 |
|
|
10 |
|
|
|
|
6 |
|
x4 |
|
|
|
12 |
8 |
|
6 |
|
|
x5 |
|
|
|
|
|
4 |
|
|
|
x6 |
|
|
|
|
|
9 |
3 |
2 |
8 |
x7 |
|
|
|
|
|
|
|
|
10 |
x8 |
|
|
|
|
|
|
|
4 |
3 |
x9 |
|
|
|
|
|
|
|
|
6 |
x10 |
|
|
Исток: x7 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
121
№ 1-23 |
№ 1-24 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
8 |
5 |
7 |
1 |
|
|
|
|
|
x2 |
|
2 |
|
|
|
|
|
3 |
|
x3 |
|
|
5 |
|
|
|
|
6 |
|
x4 |
|
|
|
8 |
2 |
|
1 |
|
|
x5 |
|
|
|
|
|
3 |
|
|
|
x6 |
|
|
|
|
|
10 |
6 |
2 |
5 |
x7 |
|
|
|
|
|
|
|
|
9 |
x8 |
|
|
|
|
|
|
|
7 |
5 |
x9 |
|
|
|
|
|
|
|
|
11 |
x10 |
|
|
Исток: x6 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
№ 1-25 |
|
|
|
|
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
2 |
9 |
2 |
6 |
|
|
|
|
|
x2 |
|
5 |
|
|
|
|
|
6 |
|
x3 |
|
|
3 |
|
|
|
|
7 |
|
x4 |
|
|
|
2 |
4 |
|
9 |
|
|
x5 |
|
|
|
|
|
6 |
|
|
|
x6 |
|
|
|
|
|
1 |
5 |
8 |
2 |
x7 |
|
|
|
|
|
|
|
|
9 |
x8 |
|
|
|
|
|
|
|
2 |
3 |
x9 |
|
|
|
|
|
|
|
|
8 |
x10 |
|
|
Исток: x1 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
4 |
7 |
1 |
3 |
|
|
|
|
|
x2 |
|
2 |
|
|
|
|
|
5 |
|
x3 |
|
|
4 |
|
|
|
|
8 |
|
x4 |
|
|
|
6 |
2 |
|
4 |
|
|
x5 |
|
|
|
|
|
2 |
|
|
|
x6 |
|
|
|
|
|
5 |
9 |
1 |
6 |
x7 |
|
|
|
|
|
|
|
|
10 |
x8 |
|
|
|
|
|
|
|
6 |
3 |
x9 |
|
|
|
|
|
|
|
|
5 |
x10 |
|
|
Исток: x1 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
№ 1-26 |
|
|
|
|
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 x10 |
|
x1 |
1 |
9 |
7 |
6 |
|
|
|
|
|
x2 |
|
1 |
|
|
|
|
|
7 |
|
x3 |
|
|
8 |
|
|
|
|
2 |
|
x4 |
|
|
|
2 |
4 |
|
3 |
|
|
x5 |
|
|
|
|
|
5 |
|
|
|
x6 |
|
|
|
|
|
9 |
1 |
7 |
5 |
x7 |
|
|
|
|
|
|
|
|
8 |
x8 |
|
|
|
|
|
|
|
6 |
3 |
x9 |
|
|
|
|
|
|
|
|
1 |
x10 |
|
|
Исток: x3 |
|
|
|
|
||
|
|
|
|
|
|
|
|||
2. Задача о графе минимальной длины
Неориентированный связный взвешенный граф задан матрицей весовых коэффициентов.
Необходимо построить новый связный граф, который содержал бы все вершины исходного графа и имел бы наименьшую сумму весов входящих в него ребер.
Исходные данные выбрать в соответствии со своим вариантом предыдущего задания.
122
3. Задача о критическом пути в графе
Дан ориентированный граф, в котором отсутствуют контуры, и каждой дуге которого приписан вес c(i, j) > 0 . Структура графа определяется
следующим условием: он имеет дугу, связывающую вершину xi с вершиной x j , если в исходных условиях задан вес c(i, j) .
Необходимо найти путь от заданной начальной вершины (истока) к заданной конечной вершине (стоку), имеющий наибольшую длину, равную сумме весов дуг, входящих в этот путь.
|
|
|
|
|
|
№ 3-1 |
|
|
с(1,2) |
= 5; |
с(1,6) = 3; |
с(1,7) = 10; |
с(2,3) = 7; с(2,7) = 14; с(2,8) = 7; |
||||
с(2,9) |
= 12; |
с(3,4) =15; |
с(3,9) = 8; |
с(4,12) = 16; |
с(5,7) = 13; |
|||
с(5,11) |
= 7; |
с(5,13) |
= 12; с(6,5) |
= 9; |
с(6,7) = 10; |
с(7,8) = 8; |
||
с(7,10) |
= 17; |
с(7,11) |
= 4; |
с(7,13) |
= 11; с(8,4) = 8; |
с(8,10) = 8; |
||
с(8,12) |
= 9; |
с(9,4) = 6; |
с(9,8) = 7; |
с(10,12) = 18; |
с(10,13) = 12; |
|||
с(11,13) = 19; с(12,13) = 6.
№ 3-2 с(1,2) = 7; с(1,6) = 2; с(1,7) = 17; с(2,3) = 4; с(2,7) = 2; с(2,8) = 12;
с(2,9) = 7; с(3,4) = 11; с(3,9) = 10; с(4,12) = 4; с(5,7) = 6; с(5,11) = 14; с (5,13) = 6; с(6,5) = 12; с(6,7) = 14; с(7,8) = 10; с(7,10) = 7; с(7,11) = 12; с(7,13) = 14; с(8,4) = 3; с(8,10) = 15; с(8,12) = 12; с(9,4) = 12; с(9,8) = 10; с(10,12) = 6; с(10,13) = 11; с(11,13) = 4; с(12,13) = 12.
|
|
|
|
|
№ 3-3 |
|
|
с(1,2) = 2; |
с(1,6) = 2; |
с(1,7) |
= 15; |
с(2,3) = 4; |
с(2,7) = 4; с(2,8) = 11; |
||
с(2,9) |
= 9; |
с(3,4) = 7; |
с(3,9) |
= 7; |
с(4,12) = 8; |
с(5,7) = 6; с(5,11) = 13; |
|
с (5,13) = 5; |
с(6,5) = 7; |
с(6,7) = 11; с(7,8) = 19; |
с(7,10) = 7; |
||||
с(7,11) = 15; с(7,13) = 11; с(8,4) = 3; |
с(8,10) = 4; с(8,12) = 12; |
||||||
с(9,4) |
= 12; |
с(9,8) = 7; |
с(10,12) = 6; |
с(10,13) = 14; с(11,13) = 11; |
|||
с(12,13) = 12. |
|
|
|
|
|
||
|
|
|
|
|
№ 3-4 |
|
|
с(1,2) |
= 4; |
с(1,6) = 5; |
с(1,7) |
= 5; |
с(2,3) = 7; с(2,7) = 2; с(2,8) = 13; |
||
с(2,9) |
= 8; |
с(3,4) = 6; |
с(3,9) |
= 11; |
с(4,12) = 4; |
с(5,7) = 14; с(5,11) = 6; |
|
с (5,13) = 8; с(6,5) = 12; |
с(6,7) = 9; |
с(7,8) = 11; |
с(7,10) = 3; |
|
с(7,11) = 4; |
с(7,13) = 9; |
с(8,4) = 11; |
с(8,10) = 12; |
с(8,12) = 7; с(9,4) = 6; |
с(9,8) = 8; |
с(10,12) = 2; |
с(10,13) = 4; |
с(11,13) = 18; с(12,13) = 11. |
|
123
№ 3-5 с(1,2) = 4; с(1,6) = 11; с(1,7) = 3; с(2,3) = 17; с(2,7) = 12; с(2,8) = 5;
с(2,9) = 8; с(3,4) = 2; с(3,9) = 10; с(4,12) = 13; с(5,7) = 14; с(5,11) = 9; с (5,13) = 7; с(6,5) = 6; с(6,7) = 10; с(7,8) = 12; с(7,10) = 7; с(7,11) = 11;
с(7,13) = 11; с(8,4) = 7; с(8,10) = 3; с(8,12) = 4; с(9,4) = 8; с(9,8) = 10; с(10,12) = 6; с(10,13) = 2; с(11,13) = 12; с(12,13) = 4.
№ 3-6 с(1,2) = 17; с(1,6) = 8; с(1,7) = 12; с(2,3) = 8; с(2,7) = 2; с(2,8) = 14;
с(2,9) = 16; с(3,4) = 15; с(3,9) = 10; с(4,12) = 6; с(5,7) = 6; с(5,11) = 13; с (5,13) = 7; с(6,5) = 19; с(6,7) = 12; с(7,8) = 10; с(7,10) = 3; с(7,11) = 11; с(7,13) = 9; с(8,4) = 8; с(8,10) = 2; с(8,12) = 6; с(9,4) = 11; с(9,8) = 7; с(10,12) = 1; с(10,13) = 5; с(11,13) = 7; с(12,13) = 12.
№ 3-7 с(1,2) =7 ; с(1,6) = 5; с(1,7) = 14; с(2,3) = 15; с(2,7) = 10; с(2,8) = 12; с(2,9) =
4; с(3,4) = 7; с(3,9) = 1; с(4,12) = 4; с(5,7) = 13; с(5,11) = 7; с(5,13) = 13; с(6,5) = 8; с(6,7) = 6; с(7,8) = 4; с(7,10) = 19; с(7,11) = 4; с(7,13) = 8; с(8,4) = 7; с(8,10) = 8; с(8,12) = 11; с(9,4) = 5; с(9,8) = 9; с(10,12) = 12; с(10,13) = 6; с(11,13) = 6; с(12,13) = 19.
№ 3-8 с(1,2) = 10; с(1,6) = 19; с(1,7) = 7; с(2,3) = 14; с(2,7) = 5; с(2,8) = 11;
с(2,9) = 6; с(3,4) = 17; с(3,9) = 8; с(4,12) = 12; с(5,7) = 13; с(5,11) = 11; с(5,13) = 9; с(6,5) = 9; с(6,7) = 10; с(7,8) = 17; с(7,10) = 4; с(7,11) = 2; с(7,13) = 11; с(8,4) = 6; с(8,10) = 18; с(8,12) = 8; с(9,4) = 8; с(9,8) = 7; с(10,12) = 9; с(10,13) = 19; с(11,13) = 7; с(12,13) = 2.
№ 3-9 с(1,2) =11; с(1,6) = 10; с(1,7) = 3; с(2,3) = 4; с(2,7) = 7; с(2,8) = 15; с(2,9) = 8;
с(3,4) = 15; с(3,9) = 11; с(4,12) = 2; с(5,7) = 6; с(5,11) = 2; с(5,13) = 2; с(6,5) = 9; с(6,7) = 8; с(7,8) = 17; с(7,10) = 6; с(7,11) = 4; с(7,13) = 11; с(8,4) = 16; с(8,10) = 13; с(8,12) = 15; с(9,4) = 2; с(9,8) = 4; с(10,12) = 18; с(10,13) = 12; с(11,13) = 6; с(12,13) = 5.
124
№ 3-10 с(1,2) = 2; с(1,6) = 5; с(1,7) = 4; с(2,3) = 6; с(2,7) = 3; с(2,8) = 2; с(2,9) = 1;
с(3,4) = 10; с(3,9) = 15; с(4,12) = 8; с(5,7) = 6; с(5,11) = 14; с(5,13) = 6; с(6,5) = 12; с(6,7) = 2; с(7,8) = 16; с(7,10) = 8; с(7,11) = 10; с(7,13) = 5; с(8,4) = 4; с(8,10) = 15; с(8,12) = 11; с(9,4) = 3; с(9,8) = 6; с(10,12) = 9; с(10,13) = 10; с(11,13) = 3; с(12,13) = 15.
№ 3-11 с(1,2) = 9; с(1,6) = 5; с(1,7) = 10; с(2,3) = 3; с(2,7) = 12; с(2,8) = 13;
с(2,9) = 7; с(3,4) = 11; с(3,9) = 9; с(4,12) = 8; с(5,7) = 5; с(5,11) = 14; с(5,13) = 7; с(6,5) = 12; с(6,7) = 13; с(7,8) = 19; с(7,10) = 8; с(7,11) = 12; с(7,13) = 14; с(8,4) = 13; с(8,10) = 17; с(8,12) = 11; с(9,4) = 11; с(9,8) = 10; с(10,12) = 6; с(10,13) = 10; с(11,13) = 4; с(12,13) = 3.
№ 3-12 с(1,2) = 10; с(1,6) = 11; с(1,7) = 12; с(2,3) = 5; с(2,7) = 7; с(2,8) = 6;
с(2,9) = 4; с(3,4) = 1; с(3,9) = 9; с(4,12) = 7; с(5,7) = 6; с(5,11) = 14; с(5,13) = 6; с(6,5) = 12; с(6,7) = 11; с(7,8) = 7; с(7,10) = 10; с(7,11) = 9; с(7,13) = 12; с(8,4) = 7; с(8,10) = 15; с(8,12) = 19; с(9,4) = 5; с(9,8) = 13; с(10,12) = 6; с(10,13) = 11; с(11,13) = 4; с(12,13) = 12.
№ 3-13 с(1,2) =5; с(1,6) = 6; с(1,7) = 7; с(2,3) = 5; с(2,7) = 6; с(2,8) = 7; с(2,9) = 8;
с(3,4) = 11; с(3,9) = 10; с(4,12) = 9; с(5,7) = 2; с(5,11) = 20; с(5,13) = 1; с(6,5) = 5; с(6,7) = 3; с(7,8) = 10; с(7,10) = 7; с(7,11) = 12; с(7,13) = 14; с(8,4) = 3; с(8,10) = 17; с(8,12) = 19; с(9,4) = 12; с(9,8) = 10; с(10,12) = 4; с(10,13) = 5; с(11,13) = 8; с(12,13) = 9.
№ 3-14 с(1,2) = 8; с(1,6) = 7; с(1,7) = 15; с(2,3) = 2; с(2,7) = 18; с(2,8) = 4; с(2,9) = 3;
с(3,4) = 19; с(3,9) = 10; с(4,12) = 5; с(5,7) = 6; с(5,11) = 12; с(5,13) = 15; с(6,5) = 7; с(6,7) = 17; с(7,8) = 10; с(7,10) = 7; с(7,11) = 13; с(7,13) = 11; с(8,4) = 2; с(8,10) = 15; с(8,12) = 10; с(9,4) = 16; с(9,8) = 10; с(10,12) = 6; с(10,13) = 11; с(11,13) = 5; с(12,13) = 10.
125
№ 3-15 с(1,2) =4 ; с(1,6) = 8; с(1,7) = 18; с(2,3) = 11; с(2,7) = 4; с(2,8) = 17;
с(2,9) = 12; с(3,4) = 15; с(3,9) = 8; с(4,12) = 7; с(5,7) = 13; с(5,11) = 11; с(5,13) = 17; с(6,5) = 4; с(6,7) = 2; с(7,8) = 18; с(7,10) = 7; с(7,11) = 5; с(7,13) = 14; с(8,4) = 3; с(8,10) = 9; с(8,12) = 3; с(9,4) = 16; с(9,8) = 5; с(10,12) = 4; с(10,13) = 14; с(11,13) = 9; с(12,13) = 3.
№ 3-16 с(1,2) = 2; с(1,6) = 3; с(1,7) = 4; с(2,3) = 5; с(2,7) = 6; с(2,8) = 7; с(2,9) = 8;
с(3,4) = 9; с(3,9) = 10; с(4,12) = 11; с(5,7) = 11; с(5,11) = 7; с(5,13) = 19; с(6,5) = 12; с(6,7) = 5; с(7,8) = 11; с(7,10) = 11; с(7,11) = 5; с(7,13) = 6; с(8,4) = 3; с(8,10) = 4; с(8,12) = 10; с(9,4) = 12; с(9,8) = 9; с(10,12) = 8; с(10,13) = 11; с(11,13) = 5; с(12,13) = 4.
№ 3-17 с(1,2) = 4; с(1,6) = 3; с(1,7) = 2; с(2,3) = 5; с(2,7) = 7;с(2,8) = 6; с(2,9) = 8;
с(3,4) = 10; с(3,9) = 11; с(4,12) = 9;с(5,7) = 12; с(5,11) = 13; с(5,13) = 16; с(6,5)= 14; с(6,7) = 15; с(7,8) = 2; с(7,10) = 17; с(7,11) = 1; с(7,13) = 8; с(8,4) = 4; с(8,10) = 6; с(8,12) = 7; с(9,4) = 4; с(9,8) = 5; с(10,12) = 8; с(10,13) = 8; с(11,13) = 10; с(12,13) = 11.
№ 3-18 с(1,2) = 10; с(1,6) = 6; с(1,7) = 11; с(2,3) = 5; с(2,7) = 9; с(2,8) = 3; с(2,9) = 8;
с(3,4) = 10; с(3,9) = 4; |
с(4,12) = 8; |
с(5,7) = 15; |
с(5,11) = 4; с(5,13) = 3; |
|
||
с(6,5) |
= 4; с(6,7) = 2; |
с(7,8) = 2; |
с(7,10) = 15; |
с(7,11) = 7; с(7,13) = 18; |
||
с(8,4) |
= |
3; с(8,10) = 12; с(8,12) = |
8; с(9,4) = 11; с(9,8) = 9; с(10,12) |
= 4; |
||
с(10,13) |
= 7; с(11,13) = 7; с(12,13) |
= 13. |
|
|
||
№ 3-19 с(1,2) = 1; с(1,6) = 9; с(1,7) = 10; с(2,3) = 9; с(2,7) = 11; с(2,8) = 2;
с(2,9) = 10; с(3,4) = 2; с(3,9) = 7; с(4,12) = 4; с(5,7) = 10; с(5,11) = 8; с(5,13) = 7; с(6,5) = 5; с(6,7) = 20; с(7,8) = 10; с(7,10) = 8; с(7,11) = 6; с(7,13) = 2; с(8,4) = 11; с(8,10) = 15; с(8,12) = 4; с(9,4) = 3; с(9,8) = 10; с(10,12) = 11; с(10,13) = 15; с(11,13) = 8; с(12,13) = 17.
126
№ 3-20 с(1,2) = 10; с(1,6) = 11; с(1,7) = 12; с(2,3) = 5; с(2,7) = 6; с(2,8) = 2;
с(2,9) = 8; с(3,4) = 9; с(3,9) = 11; с(4,12) = 13; с(5,7) = 5; с(5,11) = 9; с(5,13) = 10; с(6,5) = 17; с(6,7) = 4; с(7,8) = 3; с(7,10) = 5;
с(7,11) = 11; с(7,13) = 16; с(8,4) = 4; с(8,10) = 9; с(8,12) = 10; с(9,4) = 12; с(9,8) = 17; с(10,12) = 4; с(10,13) = 7; с(11,13) = 9; с(12,13) = 10.
№ 3-21 с(1,2) = 1; с(1,6) = 7; с(1,7) = 2; с(2,3) = 4; с(2,7) = 7; с(2,8) = 13; с(2,9) = 2;
с(3,4) = 4; с(3,9) = 8; с(4,12) = 5; с(5,7) = 2; с(5,11) = 14; с(5,13) = 6; с(6,5) = 8; с(6,7) = 10; с(7,8) = 1; с(7,10) = 6; с(7,11) = 5; с(7,13) = 12; с(8,4) = 4; с(8,10) = 9; с(8,12) = 2; с(9,4) = 2; с(9,8) = 7; с(10,12) = 12; с(10,13) = 9; с(11,13) = 1; с(12,13) = 5.
№ 3-22 с(1,2) = 7; с(1,6) = 4; с(1,7) = 4; с(2,3) = 6; с(2,7) = 3; с(2,8) = 9; с(2,9) = 2;
с(3,4) = 10; с(3,9) = 7; с(4,12) = 16; с(5,7) = 11; с(5,11) = 8; с(5,13) = 15; с(6,5) = 6; с(6,7) = 3; с(7,8) = 15; с(7,10) = 8; с(7,11) = 4; с(7,13) = 2; с(8,4) = 6; с(8,10) = 9; с(8,12) = 1; с(9,4) = 12; с(9,8) = 4; с(10,12) = 13; с(10,13) = 6; с(11,13) = 9; с(12,13) = 8.
№ 3-23 с(1,2) = 5; с(1,6) = 9; с(1,7) = 4; с(2,3) = 3; с(2,7) = 6; с(2,8) = 4; с(2,9) = 3;
с(3,4) = 15; с(3,9) = 5; с(4,12) = 6; с(5,7) = 19; с(5,11) = 15; с(5,13) = 5; с(6,5) = 2; с(6,7) = 4; с(7,8) = 7; с(7,10) = 6; с(7,11) = 3; с(7,13) = 11; с(8,4) = 8; с(8,10) = 8; с(8,12) = 16; с(9,4) = 2; с(9,8) = 7; с(10,12) = 3; с(10,13) = 9; с(11,13) = 5; с(12,13) = 9.
№ 3-24 с(1,2) =6; с(1,6) = 7; с(1,7) = 5; с(2,3) = 4; с(2,7) = 1; с(2,8) = 5; с(2,9) = 8;
с(3,4) = 11; с(3,9) = 4; с(4,12) = 7; с(5,7) = 5; с(5,11) = 3; с(5,13) = 8; с(6,5) = 5; с(6,7) = 1; с(7,8) = 12; с(7,10) = 9; с(7,11) = 4; с(7,13) = 2; с(8,4) = 7; с(8,10) = 16; с(8,12) = 8; с(9,4) = 5; с(9,8) = 6; с(10,12) = 7; с(10,13) = 12; с(11,13) = 6; с(12,13) = 3.
№ 3-25 с(1,2) = 6; с(1,6) = 1; с(1,7) = 8; с(2,3) = 4; с(2,7) = 5; с(2,8) = 11; с(2,9) = 5;
с(3,4) = 6; с(3,9) = 8; с(4,12) = 3; с(5,7) = 9; с(5,11) = 6; с(5,13) = 4; с(6,5) = 11; с(6,7) = 9; с(7,8) = 4; с(7,10) = 8; с(7,11) = 2; с(7,13) = 6;
с(8,4) = 4; с(8,10) = 15; с(8,12) = 8; с(9,4) = 10; с(9,8) = 6; с(10,12) = 12; с(10,13) = 1; с(11,13) = 5; с(12,13) = 9.
127
№ 3-26 с(1,2) = 6; с(1,6) = 8; с(1,7) = 4; с(2,3) = 1; с(2,7) = 6; с(2,8) = 4; с(2,9) = 2;
с(3,4) = 8; с(3,9) = 5; с(4,12) = 10; с(5,7) = 4; с(5,11) = 3; с(5,13) = 9; с(6,5) = 16; с(6,7) = 8; с(7,8) = 4; с(7,10) = 4; с(7,11) = 6; с(7,13) = 6; с(8,4) = 11; с(8,10) = 3; с(8,12) = 12; с(9,4) = 2; с(9,8) = 8; с(10,12) = 9; с(10,13) = 10; с(11,13) = 5; с(12,13) = 4.
4. Задача о максимальном потоке в графе (сети)
Дана транспортная сеть, представляющая собой связный ориентированный граф, состоящий из вершин и дуг, характеризуемых матрицей пропускных способностей с(i, j).
Необходимо найти такое распределение потоков по дугам графа, при котором величина потока сети Р была бы наибольшей для заданной струк-
туры графа и заданных пропускных способностей. |
|
|
|
|
|
|
||||||||||||
|
№ 4-1 |
|
|
|
|
№ 4-2 |
|
|
|
№ 4-3 |
|
|
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
50 |
20 |
|
|
|
x1 |
|
12 |
11 |
19 |
|
|
x1 |
25 |
29 |
27 |
|
|
x2 |
|
|
15 |
30 |
|
x2 |
|
|
|
10 |
7 |
|
x2 |
|
|
10 |
19 |
|
x3 |
|
|
|
|
10 |
x3 |
|
|
|
|
|
14 |
x3 |
|
|
|
|
20 |
x4 |
|
20 |
|
|
5 |
x4 |
|
|
9 |
|
13 |
|
x4 |
|
14 |
|
16 |
|
x5 |
|
|
10 |
|
15 |
x5 |
|
|
|
|
|
22 |
x5 |
|
8 |
|
|
14 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
№ 4-4 |
|
|
|
|
№ 4-5 |
|
|
|
|
№ 4-6 |
|
|
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
29 |
30 |
25 |
|
|
x1 |
|
38 |
43 |
|
|
|
x1 |
|
48 |
22 |
|
|
|
x2 |
|
|
11 |
17 |
|
x2 |
|
|
|
|
41 |
|
x2 |
|
|
|
15 |
27 |
|
x3 |
|
|
|
|
29 |
x3 |
|
|
|
18 |
|
12 |
x3 |
|
|
|
|
|
11 |
x4 |
|
15 |
|
14 |
|
x4 |
|
7 |
|
|
8 |
12 |
x4 |
|
|
25 |
|
|
6 |
x5 |
|
21 |
|
|
16 |
x5 |
|
|
|
|
|
14 |
x5 |
|
|
|
12 |
|
16 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
128
|
№ 4-7 |
|
|
|
|
№ 4-8 |
|
|
|
|
№ 4-9 |
|
|
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
21 |
12 |
19 |
|
|
x1 |
|
29 |
17 |
10 |
20 |
|
x1 |
|
45 |
33 |
22 |
|
|
x2 |
|
|
11 |
10 |
|
x2 |
|
|
|
|
8 |
19 |
x2 |
|
|
|
11 |
15 |
|
x3 |
|
|
|
|
15 |
x3 |
|
|
|
16 |
|
11 |
x3 |
|
|
|
|
|
36 |
x4 |
|
|
5 |
10 |
|
x4 |
|
|
|
|
17 |
|
x4 |
|
|
13 |
|
25 |
|
x5 |
|
|
|
|
20 |
x5 |
|
|
|
|
|
15 |
x5 |
|
|
15 |
|
|
26 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
|
№ 4-10 |
|
|
|
|
№ 4-11 |
|
|
|
|
№ 4-12 |
|
|
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
51 |
24 |
|
|
|
x1 |
|
55 |
17 |
|
|
|
x1 |
|
41 |
49 |
|
|
|
x2 |
|
|
17 |
29 |
|
x2 |
|
|
|
|
42 |
|
x2 |
|
|
|
|
45 |
|
x3 |
|
|
|
|
12 |
x3 |
|
|
|
18 |
|
35 |
x3 |
|
|
|
25 |
|
18 |
x4 |
|
27 |
|
|
7 |
x4 |
|
10 |
|
|
5 |
14 |
x4 |
|
8 |
|
|
7 |
10 |
x5 |
|
|
11 |
|
14 |
x5 |
|
|
|
|
|
11 |
x5 |
|
|
|
|
|
27 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
|
№ 4-13 |
|
|
|
|
№ 4-14 |
|
|
|
|
№ 4-15 |
|
|
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
17 |
54 |
18 |
20 |
|
x1 |
|
50 |
19 |
|
|
|
x1 |
|
37 |
27 |
17 |
|
|
x2 |
|
|
|
9 |
25 |
x2 |
|
|
|
27 |
18 |
|
x2 |
|
|
|
6 |
11 |
|
x3 |
|
|
20 |
|
14 |
x3 |
|
|
|
|
|
14 |
x3 |
|
|
|
|
|
20 |
x4 |
|
|
|
31 |
|
x4 |
|
|
15 |
|
|
10 |
x4 |
|
|
15 |
|
23 |
|
x5 |
|
|
|
|
15 |
x5 |
|
|
|
20 |
|
25 |
x5 |
|
|
|
|
|
28 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
|
№ 4-16 |
|
|
|
|
№ 4-17 |
|
|
|
|
№ 4-18 |
|
|
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
38 |
30 |
25 |
15 |
|
x1 |
|
44 |
26 |
|
|
|
x1 |
|
25 |
10 |
20 |
|
|
x2 |
|
|
|
10 |
19 |
x2 |
|
|
|
16 |
31 |
|
x2 |
|
|
|
6 |
8 |
|
x3 |
|
|
14 |
|
11 |
x3 |
|
|
|
|
|
13 |
x3 |
|
|
|
|
|
15 |
x4 |
|
|
|
15 |
|
x4 |
|
|
19 |
|
|
7 |
x4 |
|
|
7 |
|
15 |
|
x5 |
|
|
|
|
16 |
x5 |
|
|
|
11 |
|
16 |
x5 |
|
|
|
|
|
20 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
129 |
|
№ 4-19 |
|
|
|
|
№ 4-20 |
|
|
|
|
№ 4-21 |
|
|
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
35 |
45 |
|
|
|
x1 |
|
41 |
32 |
23 |
14 |
|
x1 |
|
40 |
30 |
20 |
|
|
x2 |
|
|
|
51 |
|
x2 |
|
|
|
|
14 |
20 |
x2 |
|
|
|
15 |
15 |
|
x3 |
|
|
26 |
|
16 |
x3 |
|
|
|
15 |
|
10 |
x3 |
|
|
|
|
|
30 |
x4 |
13 |
|
|
17 |
11 |
x4 |
|
|
|
|
17 |
|
x4 |
|
|
10 |
|
20 |
|
x5 |
|
|
|
|
27 |
x5 |
|
|
|
|
|
15 |
x5 |
|
|
10 |
|
|
20 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
|
№ 4-22 |
|
|
|
|
№ 4-23 |
|
|
|
|
№ 4-24 |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
25 |
40 |
|
|
|
x1 |
|
45 |
25 |
|
|
|
x1 |
|
40 |
50 |
|
|
|
x2 |
|
|
|
21 |
|
x2 |
|
|
|
10 |
35 |
|
x2 |
|
|
|
|
35 |
|
x3 |
|
|
32 |
|
19 |
x3 |
|
|
|
|
|
15 |
x3 |
|
|
|
27 |
|
12 |
x4 |
13 |
|
|
25 |
12 |
x4 |
|
|
17 |
|
|
10 |
x4 |
|
12 |
|
|
10 |
11 |
x5 |
|
|
|
|
19 |
x5 |
|
|
|
10 |
|
20 |
x5 |
|
|
|
|
|
16 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
x6 |
|
|
|
|
|
|
|
№ 4-25 |
|
|
|
|
№ 4-26 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
40 |
21 |
|
|
|
x1 |
|
20 |
17 |
|
|
|
x2 |
|
|
16 |
31 |
|
x2 |
|
|
|
|
14 |
|
x3 |
|
|
|
|
14 |
x3 |
|
|
|
24 |
|
19 |
x4 |
|
19 |
|
|
9 |
x4 |
|
30 |
|
|
10 |
22 |
x5 |
|
|
10 |
|
14 |
x5 |
|
|
|
|
|
16 |
x6 |
|
|
|
|
|
x6 |
|
|
|
|
|
|
130