Задание № 1 контрольной работы
Дан граф: |
|
|
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А |
|
|
|
|
|
|
а) превратить его во взвешенный граф с помощью персонального набора данных (в них веса горизонтальных ребер помечены буквой Х, веса вертикальных ребер – буквой Y);
б) Найти кратчайший путь (или пути) из вершины А в вершину В.
Приводим далее варианты заданий:
Вар |
Веса по оси Х |
Веса по оси Y |
1 |
56789 12221 23652 27529 26326 26272 |
29672 25361 12398 22563 82159 22232 |
2 |
28739 17593 27382 27272 18573 92221 |
37173 29853 28572 19856 27356 21272 |
3 |
29583 28573 27361 95732 28573 22527 |
29926 28719 22837 36272 19917 25282 |
4 |
96875 36572 28576 22857 25537 23282 |
22857 28831 17235 26537 28675 23292 |
5 |
36352 26372 19195 27563 28365 28252 |
28798 27526 28657 29876 29756 22282 |
6 |
11879 28735 26357 76835 29875 22262 |
21922 22776 12123 28675 28857 25262 |
7 |
52635 72756 83562 95672 93657 21227 |
92817 27528 21115 29128 29627 35276 |
8 |
12151 17812 22988 19876 95721 23229 |
28695 28628 19827 29225 28557 22282 |
9 |
52781 92629 63252 27561 62322 23567 |
61276 25329 92318 26523 82951 23282 |
10 |
28731 97513 27382 67672 98573 28793 |
37973 21853 28576 91852 27352 23562 |
11 |
21583 68573 27329 15736 28573 22186 |
61162 28791 22837 32672 91197 25227 |
12 |
12875 32576 28572 22857 65537 53827 |
22857 28839 97235 62537 28275 23528 |
13 |
99871 28735 22357 72835 21875 92622 |
29166 66772 96963 28275 68857 23227 |
14 |
34871 26731 24387 12845 61825 52623 |
27156 36472 56366 18576 78253 43526 |
15 |
56235 72752 83526 15272 13257 23557 |
12897 67528 69995 61928 61267 26282 |
16 |
96959 97896 22188 91872 15769 22221 |
28215 68228 91827 21225 68557 29222 |
17 |
51782 21212 23151 17522 21311 26292 |
22172 15312 21328 12513 81252 26223 |
18 |
18732 27523 17381 27271 28573 13562 |
37273 12853 18572 22851 17351 22252 |
19 |
12583 28573 17312 25732 18573 21627 |
22221 18722 11837 31271 22227 22272 |
20 |
21875 31572 18571 11857 25537 29372 |
11857 18832 27135 21537 18175 22362 |
21 |
31352 21371 22225 27513 18315 26658 |
28728 27511 18157 12871 22751 22272 |
22 |
22872 18735 11357 71835 12875 62227 |
12222 22771 22223 18175 28857 22628 |
23 |
52135 71751 83512 25171 23157 22175 |
21827 27518 22225 22218 22127 25292 |
24 |
22252 27822 11288 22871 25722 97282 |
18125 28118 22817 12115 28557 32571 |
25 |
32456 41267 99277 22769 24612 86271 |
97924 17997 22796 92994 17446 31469 |
При оформлении решения контрольной работы № 1, кроме стандартного титульного листа, достаточно выполнить крупный рисунок графа вместе с весами ребер и найденными по алгоритму окончательными индексами всех его вершин (рисунок можно выполнять либо вручную, либо с помощью компьютера). На рисунке требуется выделить один или несколько найденных кратчайших путей.
Пример такого оформления показан на рисунке:
34 |
2 |
24 |
8 |
32 |
2 |
34 |
5 |
39 |
2 |
35 |
|||||||||||
|
|
|
|
|
|||||||||||||||||
8 |
|
|
6 |
|
|
7 |
|
|
6 |
|
|
6 |
|
|
|
|
|||||
26 |
2 |
18 |
8 |
26 |
3 |
29 |
6 |
35 |
5 |
33 |
|||||||||||
|
|
|
|
|
|||||||||||||||||
9 |
|
|
2 |
|
|
5 |
|
|
7 |
|
|
5 |
|
|
|
|
|||||
17 |
2 |
16 |
7 |
23 |
5 |
27 |
6 |
33 |
3 |
25 |
|||||||||||
|
|
|
|
|
|||||||||||||||||
7 |
|
|
5 |
|
|
6 |
|
|
8 |
|
|
7 |
|
|
2 |
|
|||||
10 |
1 |
11 |
9 |
18 |
1 |
19 |
9 |
28 |
5 |
23 |
|||||||||||
|
|
|
|
|
|||||||||||||||||
8 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
9 |
|
|
2 |
|
|||||
2 |
2 |
4 |
6 |
10 |
3 |
13 |
7 |
19 |
2 |
|
|||||||||||
|
|
|
|
|
|||||||||||||||||
2 |
|
|
2 |
|
|
2 |
|
|
2 |
|
|
2 |
|
|
2 |
|
|||||
|
3 |
|
6 |
9 |
3 |
|
5 |
17 |
2 |
19 |
|||||||||||
2
8
21
0
3
12
Представление графов и деревьев в памяти компьютера
Задание 2. Код Харари графа.
Пусть дан неориентированный граф. Пронумеруем его вершины произвольно и составим матрицу смежности А. Поскольку для неориентированного графа она симметрична, достаточно знать её верхний треугольник А.
Расположим числа из А в виде двоичной строки (слева направо и сверху вниз). Запомним эту строку.
Меняя нумерацию вершин графа, мы получим другие двоичные строки. Сравним их между собой как двоичные числа (то есть по первому биту; при равенстве первых битов – по второму и т. д.). Наибольшее из найденных двоичных чисел называется кодом Харари, а соответствующая нумерация вершин графа – канонической. Естественно, при желании можно перевести код Харари в десятичное число.
В задании вам предстоит проделать обратный процесс.