1 Задание на работу
Задача 1
В графе (см. рис. 1.1а для вариантов 1-16 и рис. 1.1б для вариантов 17-32) с помощью алгоритма Прима найти стягивающее дерево минимального веса (в таблице 1.1 указаны веса некоторых дуг).
а) б)
Рис. 1. 1
Таблица 1.1 |
|
|
|
||||||||||||||||||
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
||||
а |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
|
||||
b |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
|
||||
|
c |
1 |
7 |
1 |
1 |
1 |
8 |
1 |
1 |
8 |
8 |
1 |
1 |
1 |
9 |
8 |
8 |
||||
|
d |
2 |
2 |
7 |
2 |
2 |
9 |
8 |
2 |
2 |
2 |
8 |
2 |
9 |
2 |
9 |
9 |
||||
|
№ варианта |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
||||
|
а |
4 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
||||
|
b |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
||||
|
c |
2 |
6 |
9 |
9 |
9 |
9 |
9 |
9 |
7 |
7 |
7 |
7 |
7 |
7 |
4 |
4 |
||||
|
d |
1 |
4 |
7 |
7 |
4 |
4 |
1 |
1 |
9 |
9 |
4 |
4 |
1 |
1 |
9 |
9 |
||||
Задача 2.
В графе (см. рис. 1.2а для вариантов 1-16 и рис. 1.26 для вариантов 17-32) с помощью алгоритма Дейкстры найти, кратчайший путь от i-й вершины-до всех остальных (в таблице 1.2 указаны номер i и веса некоторых дуг).
а) б)
Рис. 1.2
Таблица 1.2 |
|
|
|
|
|||||||||||||||||||||||||||||||||
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|||||||||||||||||||||
i |
1 |
2 |
3 |
6 |
8 |
1 |
2 |
3 |
6 |
8 |
1 |
2 |
3 |
6 |
8 |
1 |
|||||||||||||||||||||
а |
1 |
7 |
1 |
1 |
1 |
8 |
1 |
1 |
8 |
8 |
1 |
1 |
1 |
9 |
8 |
8 |
|||||||||||||||||||||
b |
2 |
2 |
7 |
2 |
2 |
9 |
8 |
2 |
2 |
2 |
8 |
2 |
9 |
2 |
9 |
9 |
|||||||||||||||||||||
c |
3 |
3 |
3 |
7 |
3 |
3 |
9 |
8 |
9 |
3 |
3 |
8 |
7 |
9 |
3 |
9 |
|||||||||||||||||||||
d |
4 |
4 |
4 |
4 |
7 |
4 |
4 |
9 |
4 |
9 |
9 |
9 |
8 |
8 |
8 |
2 |
|||||||||||||||||||||
|
№ варианта |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
|
|||||||||||||||||||
|
i |
2 |
3 |
6 |
1 |
1 |
2 |
3 |
6 |
1 |
1 |
2 |
3 |
6 |
1 |
1 |
2 |
|
|||||||||||||||||||
|
а |
4 |
6 |
9 |
9 |
9 |
9 |
9 |
9 |
7 |
7 |
7 |
7 |
7 |
7 |
4 |
4 |
|
|||||||||||||||||||
|
b |
2 |
4 |
7 |
7 |
4 |
4 |
1 |
1 |
9 |
9 |
4 |
4 |
1 |
1 |
9 |
9 |
|
|||||||||||||||||||
|
c |
2 |
2 |
4 |
1 |
7 |
1 |
4 |
7 |
1 |
4 |
1 |
9 |
9 |
4 |
7 |
1 |
|
|||||||||||||||||||
|
d |
1 |
1 |
1 |
4 |
1 |
7 |
7 |
4 |
4 |
1 |
9 |
1 |
4 |
9 |
1 |
7 |
|
|||||||||||||||||||
Задача 3.
Пусть проект описывается взвешенным графом (см. рис. 1.3а для вариантов 1-16 и рис. 1.3б для вариантов 17-32), где дуги соответствуют операциям (этапам) проекта, а вес дуги обозначает время выполнения соответствующей операции.
а)
б)
Рис. 1.3
Найти наименьшее время выполнения проекта, критические пути и резерв времени для выполнения операции ij (в таблице 1.3 указаны номера i и j и веса некоторых дуг).
Таблица 1.3 |
|
|
||||||||||||||||
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
||
i |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
||
j |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
||
а |
4 |
6 |
9 |
9 |
9 |
9 |
9 |
9 |
7 |
7 |
7 |
7 |
7 |
7 |
4 |
4 |
||
b |
2 |
4 |
7 |
7 |
4 |
4 |
1 |
1 |
9 |
9 |
4 |
4 |
1 |
1 |
9 |
9 |
||
c |
2 |
2 |
4 |
1 |
7 |
1 |
4 |
7 |
1 |
4 |
1 |
9 |
9 |
4 |
1 |
1 |
||
d |
1 |
1 |
1 |
4 |
1 |
7 |
7 |
4 |
4 |
1 |
9 |
1 |
4 |
9 |
7 |
7 |
||
№ варианта |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
||
i |
1 |
1 |
1 |
2 |
2 |
5 |
6 |
5 |
1 |
1 |
1 |
2 |
2 |
5 |
6 |
6 |
||
j |
2 |
6 |
3 |
5 |
3 |
4 |
7 |
7 |
2 |
6 |
3 |
5 |
3 |
4 |
7 |
7 |
||
а |
1 |
7 |
1 |
1 |
1 |
8 |
1 |
1 |
8 |
8 |
1 |
1 |
1 |
9 |
8 |
8 |
||
b |
2 |
2 |
7 |
2 |
2 |
9 |
8 |
2 |
2 |
2 |
8 |
2 |
9 |
2 |
9 |
9 |
||
c |
3 |
3 |
3 |
7 |
3 |
3 |
9 |
8 |
9 |
3 |
3 |
8 |
7 |
9 |
3 |
9 |
||
d |
4 |
4 |
4 |
4 |
7 |
4 |
4 |
9 |
4 |
9 |
9 |
9 |
8 |
8 |
8 |
2 |
||
Задача 4.
Найти максимальный поток в транспортной сети (см. рис. 1.4а для вариантов 1-16 и рис. 1.4б для вариантов 17-32). Число рядом с дугой есть ее пропускная способность.
а)
б)
Рис. 1.4
В таблице 1.4 указаны пропускные способности некоторых дуг.
Таблица 1.4 |
|
|
||||||||||||||||
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
||
а |
4 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
||
b |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
||
c |
2 |
6 |
9 |
9 |
9 |
9 |
9 |
9 |
7 |
7 |
7 |
7 |
7 |
7 |
4 |
4 |
||
d |
1 |
4 |
7 |
7 |
4 |
4 |
1 |
1 |
9 |
9 |
4 |
4 |
1 |
1 |
9 |
9 |
||
№ варианта |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
||
а |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
1 |
1 |
1 |
2 |
2 |
4 |
6 |
5 |
||
b |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
2 |
4 |
6 |
5 |
3 |
5 |
7 |
7 |
||
c |
1 |
7 |
1 |
1 |
1 |
8 |
1 |
1 |
8 |
8 |
1 |
1 |
1 |
9 |
8 |
8 |
||
d |
2 |
2 |
7 |
2 |
2 |
9 |
8 |
2 |
2 |
2 |
8 |
2 |
9 |
2 |
9 |
9 |
||