4.Построение графов, матриц примыканий списка примыканий
Граф – множество вершин (узлов), соединенных ребрами (дугами). Обозначение графа:G=(V,E), гдеV– множество вершин,E– множество дуг.
Ориентированный граф – граф, ребра в котором имеют направление, т.е. являются дугами.
Взвешенный граф – граф, ребра которого имеют вес, то есть числовое или логическое значение. В нашем случае весом являются интенсивность в приведенных единицах.
Матрица примыканий – двумерный массив, в котором по вертикали указывается исходные вершины, по горизонтали – конечные. В ячейках матрицы ориентированного графа ставится 0, если из соответствующей исходной вершины нельзя пройти в соответствующею конечную вершину, и 1, если из соответствующей исходной вершины можно пройти в соответствующую конечную вершину.
Ячейка матрицы взвешенного графа содержит знак бесконечности ∞, если ребро отсутствует. Во всех остальных случаях значение ячейки равно весу.
Главная диагональ матрицы содержит нули.
Список примыканий содержит все вершины графа; каждая вершина представляет собой динамически формируемый список вершин, примыкающей к ней.
Рисунок 8. Ориентированный граф.
Рисунок 9. Взвешенный граф. 21.09.12.
Рисунок 10. Взвешенный граф 5.10.12.
Список примыканий:
нулевая интенсивность на направлениях
:1 4, 3 6, 5 4, потому что на данных
участках дороги одностороннее движение;7
5 поворот запрещен на право.
Матрицы примыканий:
Московское шоссе х улица Ташкентская
Московское шоссе х улица Ташкентская 21.09.12.
Московское шоссе. х улица Ташкентская.5.10.12.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.
Михеева, Т.И. Построение математических моделей объектов улично-дорожной сети города с использованием геоинформационных технологий // Информационные технологии. 2006. №1. С. 69-75.
Михеева, Т.И., Михеев С.В. Модели наследования в системе управления дорожным движением // Информационные технологии. 2001. №7.С.50-54.