Построение графов, матриц примыканий, списка примыканий
Граф – множество вершин (узлов), соединенных ребрами (дугами). Обозначение графа G=(V, E), где V – множество вершин, E – множество дуг.
Ориентированный граф – граф, ребра в котором имеют направления, т.е. являются дугами.
Взвешенный граф – граф, ребра которого имеют вес, т.е. числовое или логическое значение. В нашем случае весом является интенсивность в приведенных единицах.
Матрица примыканий – двумерный массив, в котором по вертикали указываются исходные вершины, по горизонтали – конечные. В ячейках матрицы ориентированного графа ставится 0, если из соответствующей исходной вершины нельзя пройти в соответствующую конечную вершину, и 1, если из соответствующей исходной вершины можно пройти в соответствующую конечную вершину.
Ячейка матрицы взвешенного графа содержит знак бесконечности если ребро отсутствует. Во всех остальных случаях значение ячейки равно весу.
Главная диагональ матрицы содержит нули.
Список примыканий содержит все вершины графа; каждая вершина представляет собой динамически формируемый список вершин, примыкающих к ней.
Ориентированный граф
ул. Вольская х пр – т Кирова
проспект Кирова
к ул. Свободы
к ул. Юн. Пионеров
e9 e7
e10 e19 e20 e6
e11 e4 e5
e16 e8
e13 e12 e3
e18 e2
e 14 e17
e15
e1
Рисунок 6. Ориентированный граф.
1
2
7
11
6
5
3
3
4
7
6
11
15
10
10
9
8
7
3
11
2
11
15
3
14
14
13
12
16
15
15
7
Рисунок 7. Список примыканий
Матрица примыканий
Таблица18
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
6 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
10 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
14 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
15 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
16 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
13 сентября, вторник Таблица 19
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
1 |
∞ |
958 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
2 |
∞ |
∞ |
36 |
∞ |
∞ |
∞ |
730 |
∞ |
∞ |
∞ |
192 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
3 |
∞ |
∞ |
∞ |
884 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
4 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
5 |
∞ |
∞ |
∞ |
∞ |
∞ |
1110 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
6 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
148 |
∞ |
∞ |
∞ |
874 |
∞ |
∞ |
∞ |
88 |
∞ |
|
7 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
956 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
8 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
9 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1050 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
10 |
∞ |
∞ |
200 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
96 |
∞ |
∞ |
∞ |
754 |
∞ |
|
11 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1162 |
∞ |
∞ |
∞ |
∞ |
|
12 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
13 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
826 |
∞ |
∞ |
|
14 |
∞ |
∞ |
648 |
∞ |
∞ |
∞ |
78 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
100 |
∞ |
|
15 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
942 |
|
16 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
15 сентября, четверг, утро Таблица 20
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
1 |
∞ |
1438 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
2 |
∞ |
∞ |
4 |
∞ |
∞ |
∞ |
1134 |
∞ |
∞ |
∞ |
300 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
3 |
∞ |
∞ |
∞ |
830 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
4 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
5 |
∞ |
∞ |
∞ |
∞ |
∞ |
1410 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
6 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
208 |
∞ |
∞ |
∞ |
1128 |
∞ |
∞ |
∞ |
74 |
∞ |
|
7 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1438 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
8 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
9 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1128 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
10 |
∞ |
∞ |
248 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
76 |
∞ |
∞ |
∞ |
804 |
∞ |
|
11 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1504 |
∞ |
∞ |
∞ |
∞ |
|
12 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
13 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
730 |
∞ |
∞ |
|
14 |
∞ |
∞ |
578 |
∞ |
∞ |
∞ |
96 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
56 |
∞ |
|
15 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
934 |
|
16 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
15 сентября, четверг, вечер Таблица 21
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
1 |
∞ |
884 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
2 |
∞ |
∞ |
96 |
∞ |
∞ |
∞ |
658 |
∞ |
∞ |
∞ |
96 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
3 |
∞ |
∞ |
∞ |
1122 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
4 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
5 |
∞ |
∞ |
∞ |
∞ |
∞ |
989,2 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
6 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
200 |
∞ |
∞ |
∞ |
661,2 |
∞ |
∞ |
∞ |
128 |
∞ |
|
7 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
932 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
8 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
9 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1313,2 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
10 |
∞ |
∞ |
190 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
62 |
∞ |
∞ |
∞ |
1061,2 |
∞ |
|
11 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
853,2 |
∞ |
∞ |
∞ |
∞ |
|
12 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
13 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1050 |
∞ |
∞ |
|
14 |
∞ |
∞ |
836 |
∞ |
∞ |
∞ |
74 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
140 |
∞ |
|
15 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1329,2 |
|
16 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
20 сентября, вторник Таблица 22
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
1 |
∞ |
940 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
2 |
∞ |
∞ |
58 |
∞ |
∞ |
∞ |
696 |
∞ |
∞ |
∞ |
186 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
3 |
∞ |
∞ |
∞ |
794 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
4 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
5 |
∞ |
∞ |
∞ |
∞ |
∞ |
1228 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
6 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
28 |
∞ |
∞ |
∞ |
1030 |
∞ |
∞ |
∞ |
170 |
∞ |
|
7 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
888 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
8 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
9 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1220 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
10 |
∞ |
∞ |
132 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
284 |
∞ |
∞ |
∞ |
804 |
∞ |
|
11 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1500 |
∞ |
∞ |
∞ |
∞ |
|
12 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
13 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
946 |
∞ |
∞ |
|
14 |
∞ |
∞ |
604 |
∞ |
∞ |
∞ |
164 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
178 |
∞ |
|
15 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
1152 |
|
16 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |