Объекты и связи
Граф состоит из вершин и соединяющих их рёбер. Вершины обозначают выбранные объекты, а рёбра — отношения между ними. В дорожной модели вершинами могут быть населённые пункты, рёбрами — дороги. В модели общения вершины обозначают людей, а ребро — наличие выбранной связи.
Если связь имеет направление, используют ориентированный граф: ребро изображают стрелкой, или дугой. Например, односторонняя дорога допускает движение только в указанную сторону. Число, приписанное ребру, называют весом. Это может быть длина пути, время или стоимость; смысл веса требуется указать заранее.
Маршрут — последовательность связанных вершин и рёбер. Взвешенный граф позволяет искать путь с наименьшей суммой весов. Кратчайший по расстоянию маршрут не обязательно будет самым быстрым, если время поездки зависит от других условий.
Условная сеть дорог
Пусть неориентированный граф содержит дороги А–Б длиной 4 километра, А–В длиной 2 километра, В–Б длиной 1 километр, Б–Г длиной 3 километра и В–Г длиной 7 километров. Других дорог нет.
Путь А–Б–Г имеет длину 7 километров, А–В–Г — 9, а А–В–Б–Г — 6. Последний короче, хотя содержит больше участков. Поэтому считать только количество рёбер недостаточно, когда веса различаются.
Подобные модели помогают планировать доставку, выбирать объезд при закрытии дороги, размещать торговые точки и распределять обслуживание территории. Выводы относятся к тем свойствам, которые включены в модель.