Построение графов, матриц примыканий списка примыканий
Граф – множество вершин (узлов), соединенных ребрами (дугами). Обозначение графа: G=(V,E), где V – множество вершин, E – множество дуг.
Ориентированный граф – граф, ребра в котором имеют направление, т.е. являются дугами.
Взвешенный граф – граф, ребра которого имеют вес, то есть числовое или логическое значение. В нашем случае весом являются интенсивность в приведенных единицах.
Матрица примыканий – двумерный массив, в котором по вертикали указывается исходные вершины, по горизонтали – конечные. В ячейках матрицы ориентированного графа ставится 0, если из соответствующей исходной вершины нельзя пройти в соответствующею конечную вершину, и 1, если из соответствующей исходной вершины можно пройти в соответствующую конечную вершину.
Ячейка матрицы взвешенного графа содержит знак бесконечности ∞, если ребро отсутствует. Во всех остальных случаях значение ячейки равно весу.
Главная диагональ матрицы содержит нули.
Список примыканий содержит все вершины графа; каждая вершина представляет собой динамически формируемый список вершин, примыкающей к ней.
Ориентированный граф:
Ул. Владимирская
– ул.Коммунистическая:
Рисунок 4. Ориентированный граф
Взвешенный граф:
Ул. Владимирская – ул. Коммунистическая (утро)
Рисунок 5. Взвешенный граф
Ул. Владимирская
– ул. Коммунистическая (вечер)
Рисунок 6. Взвешенный граф
Список примыкания:
Рисунок 7. Список примыкания
Матрицы примыканий:
Ул. Владимирская – ул. Коммунистическая
Таблица 11
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
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 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||