Задания к практической работе № 2 по основам теоргии графов

1. Задания к практической работе № 2 по основам теории графов

Алгоритм и задача Прима и
задача о назначениях с
взвешенными ребрами графа

2. Вариант №1

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
2
6
3
10
1
17
12
4
13
5
0
0
4
0
4
12
7
∞
5
19
18
1
0
0
3
7
0
11
10
8
13
6
0
2
4
3
0
0
5
12
4
3
9
20
2
6
0
7
0
0
5
14
∞
16
∞
17
14
3
4
0
5
5
0
13
8
∞
12
4
15

3. Вариант №2

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
2
6
3
15
14
11
12
10
13
5
0
0
4
0
4
4
16
19
14
16
18
1
0
0
3
7
0
13
20
15
13
12
11
2
4
3
0
0
5
22
4
3
17
10
14
6
0
7
0
0
5
10
7
9
11
13
25
3
4
0
5
5
0
14
28
13
12
5
8

4. Вариант №3

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
2
6
3
10
25
10
12
16
10
5
0
0
4
0
4
5
8
7
5
27
4
1
0
0
3
7
0
17
9
6
3
7
0
2
4
3
0
0
5
12
14
3
2
10
19
6
0
7
0
0
5
9
30
47
14
10
15
3
4
0
5
5
0
20
14
0
9
15
11

5. Вариант №4

Решить алгоритмом Прима
Решить задачу о назначениях
0
8
9
2
2
3
12
13
11
20
16
14
8
0
0
4
0
8
14
10
10
14
10
17
9
0
0
23
27
0
10
20
19
13
17
15
2
4
23
0
0
9
11
14
13
11
17
19
2
0
27
0
0
15
15
12
18
14
18
12
3
8
0
9
15
0
13
15
20
17
16
13

6. Вариант №5

Решить алгоритмом Прима
Решить задачу о назначениях
0
45
51
42
36
33
19
15
21
22
26
23
45
0
0
34
0
38
15
20
9
4
7
8
51
0
0
43
27
0
25
10
30
13
41
20
42
34
43
0
0
39
22
14
3
14
12
19
36
0
27
0
0
35
26
9
45
6
32
35
33
38
0
39
35
0
23
18
10
19
30
20

7. Вариант №6

Решить алгоритмом Прима
Решить задачу о назначениях
0
1
11
12
4
13
9
10
11
12
16
13
1
0
0
4
0
8
10
3
5
4
10
8
11
0
0
3
6
0
1
20
8
3
7
0
12
4
3
0
0
2
2
14
3
4
10
11
4
0
6
0
0
4
6
7
17
9
7
15
13
8
0
2
4
0
3
18
0
10
5
5

8. Вариант №7

Решить алгоритмом Прима
Решить задачу о назначениях
0
4
1
2
0
3
30
35
31
32
36
43
4
0
0
4
0
8
25
40
40
34
30
38
1
0
0
3
2
0
40
30
20
33
37
20
2
4
3
0
0
1
22
34
33
25
10
39
0
0
2
0
0
5
36
10
37
30
32
35
3
8
0
1
5
0
33
38
20
39
45
37

9. Вариант №8

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
0
12
6
0
21
15
22
33
16
23
5
0
0
4
0
4
25
24
10
24
∞
28
0
0
0
3
7
0
21
20
20
33
27
20
12
4
3
0
0
9
32
24
23
20
30
29
6
0
7
0
0
15
26
30
27
10
30
25
0
4
0
9
15
0
33
28
40
29
35
40

10. Вариант №9

Решить алгоритмом Прима
0
14
10
11
15
13
14
0
0
14
0
17
10
0
0
13
17
0
11
14
13
0
0
19
15
0
17
0
0
16
13
17
0
19
16
0
Решить задачу о назначениях
18
3
10
12
6
9
13
10
10
4
10
8
10
20
7
3
7
10
2
4
3
2
30
6
6
10
7
10
9
5
∞
8
20
6
5
4

11. Вариант №10

Решить алгоритмом Прима
Решить задачу о назначениях
0
15
21
22
26
23
10
12
11
2
16
13
15
0
0
4
0
8
13
11
10
14
∞
8
21
0
0
3
41
0
12
∞
12
13
17
19
22
4
3
0
0
19
12
4
7
13
10
9
26
0
41
0
0
35
17
20
16
11
14
15
23
8
0
19
35
0
14
18
16
9
12
13

12. Вариант №11

Решить алгоритмом Прима
Решить задачу о назначениях
0
0
1
2
6
3
10
15
11
12
16
14
0
0
0
4
0
8
5
7
10
14
10
15
1
0
0
3
7
0
21
10
8
3
7
11
2
4
3
0
0
0
22
9
13
9
19
9
6
0
7
0
0
5
26
∞
17
20
11
12
3
8
0
0
5
0
10
25
10
9
2
12

13. Вариант №12

Решить алгоритмом Прима
Решить задачу о назначениях
0
35
31
22
36
33
19
25
11
22
16
3
35
0
0
34
0
38
15
18
20
14
∞
8
31
0
0
33
37
0
10
10
17
13
9
10
22
34
33
0
0
39
12
14
3
16
20
9
36
0
37
0
0
35
16
10
7
18
15
5
33
38
0
39
35
0
13
8
17
19
15
24

14. Вариант №13

Решить алгоритмом Прима
Решить задачу о назначениях
0
25
21
32
16
23
3
20
12
12
14
13
25
0
0
24
0
28
10
2
10
24
∞
8
21
0
0
23
27
0
11
20
12
3
7
20
32
24
23
0
0
29
9
14
3
4
20
19
16
0
27
0
0
35
18
10
7
10
5
15
23
28
0
29
35
0
7
18
30
19
15
10

15. Вариант №14

Решить алгоритмом Прима
Решить задачу о назначениях
0
3
1
2
6
0
11
∞
10
2
6
13
3
0
0
4
10
8
10
9
10
4
20
8
1
0
0
3
7
0
10
∞
12
13
7
∞
2
4
3
0
0
6
2
4
13
8
9
9
6
10
7
0
0
5
6
∞
7
∞
3
15
0
8
0
6
5
0
3
8
12
9
15
17

16. Вариант №15

Решить алгоритмом Прима
Решить задачу о назначениях
0
12
11
2
16
13
16
5
21
12
6
13
12
0
0
14
0
8
15
25
∞
4
∞
8
11
0
0
13
17
0
17
10
13
3
17
4
2
14
13
0
10
9
12
24
3
19
0
9
16
0
17
10
0
15
16
20
24
∞
22
25
13
8
0
9
15
0
13
8
14
19
15
27

17. Вариант №16

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
2
6
4
7
7
11
2
16
3
5
0
10
4
0
5
17
3
8
14
20
8
1
10
0
3
7
0
10
8
7
3
17
10
2
4
3
0
0
9
12
4
3
9
8
9
6
0
7
0
0
2
6
8
7
10
12
14
4
5
0
9
2
0
13
8
11
9
5
3

18. Вариант №17

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
2
6
3
9
15
11
12
16
13
5
0
0
4
0
8
5
12
10
4
∞
19
1
0
0
3
7
0
10
∞
6
4
17
12
2
4
3
0
0
9
2
14
3
18
7
18
6
0
7
0
0
5
15
10
18
16
11
5
3
8
0
9
5
0
3
18
14
19
15
12

19. Вариант №18

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
2
6
3
15
16
10
12
16
13
5
0
0
4
0
8
14
17
20
15
∞
8
1
0
0
3
7
0
11
10
19
14
7
∞
2
4
3
0
0
9
13
14
13
12
19
9
6
0
7
0
0
5
15
10
17
20
13
12
3
8
0
9
5
0
12
18
10
9
15
14

20. Вариант №19

Решить алгоритмом Прима
Решить задачу о назначениях
0
15
10
12
6
13
15
16
10
12
16
13
15
0
0
14
0
8
14
17
20
15
∞
8
10
0
0
3
7
0
11
10
19
14
7
∞
12
14
3
0
0
9
13
14
13
12
19
9
6
0
7
0
0
5
15
10
17
20
13
12
13
8
0
9
5
0
12
18
10
9
15
14

21. Вариант №20

Решить алгоритмом Прима
Решить задачу о назначениях
0
0
11
2
8
3
40
45
51
42
36
33
0
0
0
4
0
8
45
30
∞
34
10
38
11
0
0
3
7
0
51
∞
35
43
27
∞
2
4
3
0
10
19
42
34
43
49
20
39
8
0
7
10
0
15
36
∞
27
∞
40
35
3
8
0
19
15
0
33
38
0
39
35
37

22. Вариант №21

Решить алгоритмом Прима
Решить задачу о назначениях
0
0
10
2
6
3
10
8
9
22
12
9
0
0
0
4
0
8
18
20
17
14
10
8
10
0
0
13
7
0
19
∞
10
23
27
∞
2
4
13
0
0
9
12
4
23
8
0
9
6
0
7
0
0
15
2
∞
27
20
6
15
3
8
0
9
15
0
3
17
∞
19
15
17

23. Вариант №22

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
12
6
13
5
0
0
4
0
8
1
0
0
3
7
4
12
4
3
0
0
9
6
0
7
0
0
5
13
8
4
9
5
0
16
5
1
12
6
3
5
12
∞
4
10
4
11
15
8
3
17
0
2
14
3
9
20
5
6
∞
7
18
24
5
3
14
10
5
15
22

24. Вариант №23

Решить алгоритмом Прима
Решить задачу о назначениях
0
7
1
2
6
3
11
15
11
2
6
3
7
0
8
4
0
8
5
10
17
4
9
4
1
8
0
3
7
0
1
10
2
3
7
20
2
4
3
0
0
9
2
14
13
8
12
25
6
0
7
0
0
5
6
10
4
10
9
8
3
8
0
9
5
0
7
14
10
5
5
3

25. Вариант №24

Решить алгоритмом Прима
Решить задачу о назначениях
0
5
1
2
6
3
5
0
0
4
0
8
1
0
0
3
7
4
2
4
3
0
7
9
6
0
7
7
0
5
3
8
4
9
5
0
9
5
11
2
6
4
7
2
10
14
20
5
1
9
8
3
7
10
2
4
3
10
8
7
8
10
6
7
12
5
3
4
20
5
5
7