2015-06-30
278
Потоки в транспортных сетях
Графы и сети
Определение.
С формальной точки зрения граф представляет собой упорядоченную пару 
множеств, первое из которых состоит из вершин или узлов графа, а второе – из его рёбер или дуг.
Ребро связывает между собой две вершины. При работе с графами часто возникает вопрос, как проложить путь из рёбер (или дуг) от одной вершины графа к другой? Поэтому в дальнейшем целесообразно говорить о движении по ребру. Это означает, что имеет место переход из вершины А графа в другую вершину В, связанную с ней ребром АВ. (При этом ребро графа, связывающее две вершины, для краткости обозначается парой этих вершин АВ, Рисунок 1).
Рисунок 1 – Простейший граф: две вершины А и В, соединённые дугой АВ
Граф может быть ориентированным (орграфом) и не ориентированным. Рёбра не ориентированного графа, чаще всего называемого просто графом, можно проходить в обоих направлениях. В этом случае ребро графа – это неупорядоченная пара вершин или его концов.
В ориентированном графе, или орграфе, рёбра представляют собой упорядоченные пары вершин: первая вершина – это начало ребра; а вторая – его конец. Начало и конец ребра в ориентированном графе также могут совпадать.
