8-ЗАДАЧА О МНОГОПОЛЮСНОЙ ЦЕПИ
.docИтерация 5:
Матрица пропускных способностей |
Матрица маршрутов |
|
||||||||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
1 |
0 |
12 |
30 |
19 |
11 |
9 |
- |
|
1 |
1 |
4 |
3 |
3 |
4 |
4 |
7 |
||
2 |
12 |
0 |
12 |
12 |
11 |
9 |
- |
|
2 |
4 |
2 |
4 |
4 |
4 |
4 |
7 |
||
3 |
30 |
12 |
0 |
19 |
11 |
9 |
- |
|
3 |
1 |
4 |
3 |
4 |
4 |
4 |
7 |
||
4 |
19 |
12 |
19 |
0 |
11 |
9 |
- |
|
4 |
3 |
2 |
3 |
4 |
5 |
6 |
7 |
||
5 |
11 |
11 |
11 |
11 |
0 |
9 |
- |
|
5 |
4 |
4 |
4 |
4 |
5 |
4 |
7 |
||
6 |
9 |
9 |
9 |
9 |
9 |
0 |
- |
|
6 |
4 |
4 |
4 |
4 |
4 |
6 |
7 |
||
7 |
19 |
12 |
19 |
20 |
11 |
9 |
0 |
|
7 |
4 |
4 |
4 |
4 |
4 |
4 |
7 |
||
Итерация 6:
Матрица пропускных способностей |
Матрица маршрутов |
|
||||||||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
1 |
0 |
12 |
30 |
19 |
11 |
9 |
- |
|
1 |
1 |
4 |
3 |
3 |
4 |
4 |
7 |
||
2 |
12 |
0 |
12 |
12 |
11 |
9 |
- |
|
2 |
4 |
2 |
4 |
4 |
4 |
4 |
7 |
||
3 |
30 |
12 |
0 |
19 |
11 |
9 |
- |
|
3 |
1 |
4 |
3 |
4 |
4 |
4 |
7 |
||
4 |
19 |
12 |
19 |
0 |
11 |
9 |
- |
|
4 |
3 |
2 |
3 |
4 |
5 |
6 |
7 |
||
5 |
11 |
11 |
11 |
11 |
0 |
9 |
- |
|
5 |
4 |
4 |
4 |
4 |
5 |
4 |
7 |
||
6 |
9 |
9 |
9 |
9 |
9 |
0 |
- |
|
6 |
4 |
4 |
4 |
4 |
4 |
6 |
7 |
||
7 |
19 |
12 |
19 |
20 |
11 |
9 |
0 |
|
7 |
4 |
4 |
4 |
4 |
4 |
4 |
7 |
||
Итерация 7:
Матрица пропускных способностей |
Матрица маршрутов |
|
||||||||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
1 |
0 |
12 |
30 |
19 |
11 |
9 |
- |
|
1 |
1 |
4 |
3 |
3 |
4 |
4 |
7 |
||
2 |
12 |
0 |
12 |
12 |
11 |
9 |
- |
|
2 |
4 |
2 |
4 |
4 |
4 |
4 |
7 |
||
3 |
30 |
12 |
0 |
19 |
11 |
9 |
- |
|
3 |
1 |
4 |
3 |
4 |
4 |
4 |
7 |
||
4 |
19 |
12 |
19 |
0 |
11 |
9 |
- |
|
4 |
3 |
2 |
3 |
4 |
5 |
6 |
7 |
||
5 |
11 |
11 |
11 |
11 |
0 |
9 |
- |
|
5 |
4 |
4 |
4 |
4 |
5 |
4 |
7 |
||
6 |
9 |
9 |
9 |
9 |
9 |
0 |
- |
|
6 |
4 |
4 |
4 |
4 |
4 |
6 |
7 |
||
7 |
19 |
12 |
19 |
20 |
11 |
9 |
0 |
|
7 |
4 |
4 |
4 |
4 |
4 |
4 |
7 |
||
ПРИМЕР 2. Транспортировка космического корабля
Рис. 1. Допустимые нагрузки на мосты. |
Таблица 2. Маршруты с максимальной пропускной способностью
Источник |
сток |
Максимальная пропускная способность |
1 |
13 |
47 |
2 |
13 |
49 |
3 |
13 |
49 |
1 |
14 |
47 |
2 |
14 |
48 |
3 |
14 |
47 |
1 |
15 |
47 |
2 |
15 |
48 |
3 |
15 |
47 |
Исходная матрица
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
1 |
0 |
99 |
99 |
45 |
47 |
99 |
99 |
99 |
99 |
99 |
47 |
39 |
47 |
47 |
47 |
2 |
99 |
0 |
99 |
53 |
50 |
48 |
99 |
9 |
99 |
99 |
48 |
39 |
49 |
48 |
48 |
3 |
99 |
99 |
0 |
99 |
41 |
49 |
99 |
99 |
99 |
99 |
47 |
39 |
49 |
47 |
47 |
4 |
99 |
99 |
99 |
0 |
99 |
53 |
49 |
99 |
99 |
99 |
47 |
39 |
49 |
47 |
47 |
5 |
99 |
99 |
99 |
99 |
0 |
99 |
99 |
40 |
48 |
99 |
48 |
99 |
47 |
48 |
48 |
6 |
99 |
99 |
99 |
53 |
99 |
0 |
99 |
99 |
41 |
39 |
47 |
39 |
49 |
47 |
47 |
7 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
51 |
99 |
99 |
47 |
99 |
50 |
47 |
47 |
8 |
99 |
99 |
99 |
99 |
99 |
99 |
51 |
0 |
47 |
99 |
47 |
99 |
50 |
47 |
47 |
9 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
47 |
0 |
99 |
52 |
99 |
47 |
52 |
49 |
10 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
48 |
999 |
48 |
43 |
11 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
47 |
57 |
99 |
12 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
53 |
43 |
13 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
99 |
14 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
15 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
Матрица пропускных способностей дуг
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
1 |
0 |
99 |
99 |
45 |
47 |
45 |
47 |
47 |
47 |
39 |
99 |
99 |
99 |
99 |
99 |
2 |
99 |
0 |
99 |
53 |
50 |
53 |
49 |
49 |
48 |
39 |
99 |
99 |
99 |
99 |
99 |
3 |
99 |
99 |
0 |
49 |
41 |
49 |
49 |
49 |
47 |
39 |
99 |
99 |
99 |
99 |
99 |
4 |
99 |
99 |
99 |
0 |
99 |
53 |
49 |
49 |
47 |
39 |
99 |
99 |
99 |
99 |
99 |
5 |
99 |
99 |
99 |
99 |
0 |
99 |
47 |
47 |
48 |
99 |
99 |
99 |
99 |
99 |
99 |
6 |
99 |
99 |
99 |
53 |
99 |
0 |
49 |
49 |
47 |
39 |
99 |
99 |
99 |
99 |
99 |
7 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
51 |
47 |
99 |
45 |
99 |
50 |
99 |
99 |
8 |
99 |
99 |
99 |
99 |
99 |
99 |
51 |
0 |
47 |
99 |
46 |
99 |
99 |
99 |
99 |
9 |
99 |
99 |
99 |
99 |
99 |
99 |
47 |
47 |
0 |
99 |
52 |
99 |
99 |
99 |
49 |
10 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
48 |
99 |
99 |
99 |
11 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
47 |
57 |
99 |
12 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
53 |
43 |
13 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
99 |
14 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |
99 |
15 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
99 |
0 |