Основные определения. Ребро в графе G может быть ориентированным и иметь начало и конец

Ребро в графе G может быть ориентированным и иметь начало и конец. Такое ребро называется дугой, а граф, содержащий дуги, называется ориентированным, или орграфом. На рисунке дуга изображается стрелкой.

Многие понятия, введенные для неографов, для орграфов приобретают другое определение. Матрица расстояний для орграфа несимметрична, и эксцентриситет вершины зависит от того, как выбирается максимум. Если максимум ищется в строке, то эксцентриситет вершины называется числом внешнего разделения, а если в столбце – числом внутреннего разделения. Соответственно определяются внешний и внутренний центры.

Основание орграфа – неограф с теми же вершинами, но ребрами вместо соответствующих дуг.

Маршрут в орграфе – последовательность вершин, соединенных дугами, направленными в одну сторону.

Маршрут, в котором все дуги разные, есть путь.

Путь, в котором начало и конец совпадают, есть контур. Длина пути измеряется числом входящих в него дуг, а для взвешенного орграфа – это сумма весов дуг.

В орграфе две локальные степени вершины v: – число дуг, входящих в v, и – число дуг, выходящих из v. Лемма о рукопожатиях для орграфа имеет вид

, (13.1)

где суммирование производится по всем вершинам графа.

Множество вершин v, образующих дугу [ v, u ] с вершиной u, называется множеством предшественников вершины u, а множество вершин u, образующих дугу [ v, u ] с вершиной v, называется множеством преемников вершины v. Мощности этих множеств соответственно равны: , .

В дальнейшем под графом будем понимать как неограф, так и орграф.