Сетевые модели. Графы

При табличном моделировании сложных систем модели могут оказаться слишком большими и неудобными для использования. В сетевых моделях компактно отображаются наиболее существенные отношения между объектами. Обычно сетевые модели изображаются в наглядном графическом виде.

Пример сетевой модели – схема линий метрополитена.

Распространенной формой представления сетевых моделей являются графы.

Граф представляет собой наглядное описание отношений (связей) между парами элементов некоторого множества. Эти элементы называются вершинами графа и обычно изображаются окружностями или прямоугольниками. Связи между вершинами называются ребрами и изображаются линиями. Название вершины пишется внутри ее изображения или рядом с ним. Две соединенные ребром вершины называются смежными. В информационном моделировании систем вершинам графа обычно соответствуют входящие в систему объекты, а ребрам – отношения между ними.

Вершины этого графа – элементы множества населенных пунктов некоторого региона. То, что две вершины соединены ребром, означает наличие дороги между соответствующими населенными пунктами. Форма ребра и расположение вершин графа влияют только на наглядность изображения графа и несущественны для информационной модели.

Граф с дополнительной информацией о связях называется нагруженным графом.

Пример (рис.1). Нагруженный граф дорог с указанием стоимости проезда между населенными пунктами:

Рисунок 1

Если отношения между объектами моделируемой системы не являются симметричными, например, есть проезд из A в B, но нет проезда из B в А, то для их изображения используются линии со стрелками на конце, называемые не ребрами, а дугами. Граф, в состав которого входят дуги, называется ориентированным. Ориентированный граф тоже может быть нагруженным.

Пример (рис2): Ориентированный нагруженный граф стоимости перевозок между населенными пунктами.

Рисунок 2

Смежными называются вершины графа, соединённые ребром, говорят – пара смежных вершин.

Поиск по сайту: