Завдання до розділу „Теорія графів”
Граф задано К-списком
.
Намалювати його, записати його матрицю суміжності та знайти:
Кількість шляхів довжини 3, що зв’язують вершину 1.
Кількість шляхів довжини 2, що зв’язують вершину 2 з вершиною 4.
Кількість всіх можливих циклів довжини 3.
Кількість циклів довжини 3, що зв’язують вершину 5.
Кількість шляхів довжини 3, що зв’язують вершину 3 з вершиною 5.
Кількість шляхів довжини 3, що зв’язують вершину 6.
Кількість шляхів довжини 2, що зв’язують вершину 3 з вершиною 5.
Кількість шляхів довжини 3, що зв’язують вершину 1 з вершиною 5.
Кількість шляхів довжини 3, що зв’язують вершину 4.
Кількість шляхів довжини 3, що зв’язують вершину 2.
Кількість шляхів довжини 3, що зв’язують вершину 2 з вершиною 5.
Кількість шляхів довжини 2, що зв’язують вершину 4.
Кількість шляхів довжини 3, що зв’язують вершину 1 з вершиною 5.
Кількість циклів довжини 3, що зв’язують вершину 5.
Кількість шляхів довжини 2, що зв’язують вершину 4.
Кількість шляхів довжини 3, що зв’язують вершину 3 з вершиною 5.
Кількість всіх шляхів довжини 3 даного графа.
Кількість шляхів довжини 3, що зв’язують вершину 1 з вершиною 6.
Кількість шляхів довжини 2, що зв’язують вершину 4 з вершиною 6.
Кількість всіх шляхів довжини 1, 2, 3, що зв’язують вершину 2 з іншими.
Кількість шляхів довжини 2 і 3, що зв’язують вершину 4 з іншими.
Кількість шляхів довжини 3, що зв’язують вершину 2 з вершиною 5.
Кількість шляхів довжини 3, що зв’язують вершину 6.
Кількість шляхів довжини 3, що зв’язують вершину 3 з вершиною 6.
Кількість контурів довжини 3, що зв’язують вершину 4.
Кількість шляхів довжини 2, що зв’язують вершину 6 з вершиною 2.
Кількість шляхів довжини 3, що зв’язують вершину 5 з вершиною 3.
Кількість шляхів довжини 3, що зв’язують вершину 4 з вершиною 5.
Кількість шляхів довжини 2, що зв’язують вершину 6 з вершиною 1.
Кількість шляхів довжини 3, що зв’язують вершину 6
Орграф, що має 11 вершин (0..10), задано матрицею суміжності.
Зобразити
цей граф. Знайти найкоротший шлях у
незваженому графі з вершини i
у
вершину
j,
де
,
,
–
номер
варіанту.
Знайти найкоротший шлях у зваженому графі з вершини
у вершину
,
що має 11 вершин (0..10), заданий матрицею
суміжності,
вага
дуги якого
визначається співвідношенням
,
де
,
,
–
номер варіанту
–
номер вершини, з якої виходить дуга,
–
номер вершини, в яку входить дуга.
Знайти максимальну досконалу паракомбінацію:
а) у дводольному графі
б) у звичайному графі
Знайти максимальний потік у траспортній мережі методом Форда-Фалкерсона.
№ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
9 |
7 |
11 |
3 |
15 |
25 |
4 |
8 |
10 |
11 |
9 |
7 |
8 |
11 |
15 |
9 |
20 |
21 |
2 |
7 |
6 |
12 |
5 |
16 |
20 |
4 |
18 |
10 |
12 |
9 |
6 |
8 |
12 |
16 |
19 |
22 |
25 |
3 |
8 |
11 |
10 |
13 |
14 |
21 |
14 |
9 |
12 |
10 |
19 |
8 |
18 |
10 |
15 |
13 |
19 |
22 |
4 |
4 |
7 |
10 |
3 |
5 |
25 |
9 |
10 |
15 |
12 |
9 |
17 |
8 |
15 |
5 |
9 |
20 |
21 |
5 |
9 |
6 |
15 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
26 |
21 |
6 |
9 |
8 |
10 |
9 |
15 |
25 |
44 |
8 |
10 |
11 |
9 |
17 |
8 |
11 |
15 |
9 |
20 |
21 |
7 |
9 |
9 |
15 |
13 |
13 |
24 |
12 |
18 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
21 |
20 |
8 |
10 |
16 |
15 |
10 |
10 |
24 |
11 |
8 |
13 |
15 |
16 |
9 |
10 |
17 |
15 |
10 |
22 |
25 |
9 |
9 |
10 |
12 |
13 |
15 |
24 |
12 |
8 |
13 |
13 |
6 |
19 |
10 |
17 |
15 |
13 |
28 |
21 |
10 |
9 |
16 |
5 |
13 |
10 |
24 |
12 |
18 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
12 |
26 |
21 |
11 |
9 |
10 |
13 |
13 |
12 |
24 |
10 |
10 |
13 |
15 |
6 |
8 |
10 |
17 |
15 |
10 |
20 |
21 |
12 |
8 |
6 |
15 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
20 |
21 |
13 |
9 |
10 |
16 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
19 |
10 |
17 |
15 |
10 |
20 |
26 |
14 |
9 |
16 |
5 |
14 |
10 |
26 |
12 |
18 |
17 |
15 |
16 |
9 |
10 |
7 |
15 |
11 |
26 |
21 |
15 |
9 |
6 |
5 |
3 |
10 |
14 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
16 |
21 |
16 |
8 |
6 |
15 |
13 |
10 |
24 |
13 |
8 |
13 |
15 |
6 |
9 |
10 |
16 |
15 |
10 |
20 |
21 |
17 |
7 |
6 |
16 |
19 |
10 |
24 |
12 |
8 |
13 |
25 |
6 |
9 |
19 |
17 |
15 |
19 |
26 |
21 |
18 |
10 |
6 |
15 |
13 |
10 |
14 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
16 |
21 |
19 |
9 |
9 |
15 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
15 |
22 |
21 |
20 |
9 |
6 |
5 |
13 |
13 |
24 |
12 |
10 |
13 |
15 |
6 |
19 |
10 |
17 |
15 |
10 |
16 |
25 |
21 |
9 |
8 |
7 |
13 |
10 |
24 |
16 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
16 |
21 |
22 |
9 |
6 |
15 |
13 |
10 |
22 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
20 |
20 |
23 |
9 |
9 |
9 |
3 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
7 |
15 |
10 |
16 |
21 |
24 |
9 |
16 |
5 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
7 |
15 |
10 |
26 |
21 |
25 |
9 |
6 |
5 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
22 |
21 |
26 |
9 |
6 |
8 |
13 |
10 |
14 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
18 |
15 |
18 |
26 |
21 |
27 |
8 |
9 |
7 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
16 |
19 |
28 |
9 |
6 |
5 |
13 |
10 |
14 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
10 |
26 |
21 |
29 |
9 |
9 |
15 |
13 |
10 |
24 |
12 |
8 |
13 |
15 |
6 |
9 |
10 |
17 |
15 |
15 |
29 |
21 |
30 |
7 |
6 |
15 |
13 |
10 |
24 |
12 |
9 |
13 |
15 |
6 |
9 |
10 |
17 |
9 |
10 |
26 |
21 |
