Определение. Ориентированным графом (или орграфом) называется пара множеств, первое из которых представляет собой конечное непустое множество V, называемое множеством вершин, второе – множество Е, представляющее собой совокупность упорядоченных пар элементов из множества V, называемое множеством ориентированных рёбер (или просто рёбер, если известно, что граф ориентирован).
Определение. Элемент множества Е называется ориентированным ребром (или просто ребром, если известно, что граф ориентирован). Довольно часто элемент ориентированного графа называется дугой.
Обозначение. Ориентированный граф обозначается G(V,E), а для записи нескольких различных графов рекомендуется указывать, какому графу соответствует множество вершин или рёбер, например, запись V(G1) означает, что множество вершин соответствует ориентированному графу G1, запись E(G2) — что множество рёбер соответствует ориентированному графу G2.
Определение. Число вершин ориентированного графа n называется порядком этого графа, другими словами, порядок ориентированного графа определяется по мощности множества вершин графа. Определение. Ориентированный граф с n вершинами и m рёбрами называется (n, m)-орграфом.
Определение. Элементы а и b множества V называются соединёнными или связанными ребром (а, b), если (а, b) принадлежит Е.
Изображение ориентированного графа. Наглядно ориентированный граф изображается в виде рисунка (схемы или диаграммы), на котором вершины графа изображаются в виде точек (кружочков закрашенных или полых), ориентированные рёбра —– в виде направленных отрезков (стрелок), связывающих соответствующие вершины, соединённые этим ориентированным ребром. При изображении ориентированного графа не имеют значения радиус кружочков, изображающих вершины, а также длины стрелок, соответствующих ориентированным рёбрам. Позже будут рассмотрены другие способы задания ориентированных графов.
Определение. Размеченным орграфом называется ориентированный граф, в котором каждая вершина графа отмечена, т. е. задана так называемая функция разметки, которая каждой вершине (ориентированному ребру) ставит в соответствие метку (обозначение вершины или ориентированного ребра). Множество меток может разделяться на два непересекающихся подмножества: множество меток вершин и множество меток ориентированных рёбер. Заметим, что, конечно, чаще всего имеют дело именно с размеченными орграфами из соображений удобства.
Пример. Ориентированный граф G1, показанный ниже, состоит из множества вершин V(G1), содержащего 6 элементов, и множества рёбер E(G1), содержащего 6 элементов: V(G1) = {a, b, c, d, e, f}, E(G1) = {(a, b), (a, c), (b, d), (c, d), (e, c), (f, d)}.
Ориентированный граф G2, показанный ниже, состоит из множества вершин V(G2), содержащего 6 элементов, и множества рёбер E(G2), содержащего 5 элементов: V(G2) = {a, b, c, d, e, f}, E(G2) = {(a, c), (b, e), (c, d), (d, e), (f, d)}.
Замечание. Любому неориентированному графу можно поставить в соответствие неориентированный граф, придав каждому неориентированному ребру одно из двух возможных направлений. Таким образом, имеется 2 в степени n различных орграфов, если n —– число вершин.
Упражнение. Для следующих графов предлагается записать множество вершин и множество рёбер.