Ориентированные маршруты, пути и контуры

Локальная структура орграфов

Рассмотрим термины, полезные для описания некоторых структурных свойств ориентированных графов и не используемые в неориентированном случае. Если а₁@(v, w) и а₂@(v, w), то дуги а₁ и а₂ называются строго параллельными. Если а₃@(v, w), то а₁ и а₃ не строго параллельны. Если а @(v, w), то говорят, что дуга а направлена от вершины v к вершине w. Дуга а считается положительно инцидентной ее конечной вершине w. Число дуг, положительно инцидентных вершине v, называется положительной степенью v и обозначается через d⁺(v). Отрицательная степень v определяется аналогично и обозначается d^-(v). (Ориентированная петля, инцидентная v, считается положительно и отрицательно инцидентной с v.) Индексированные степени вершинd⁺(v) и d^-(v), очевидно, связаны с введенной ранее степенью d(v) следующим образом: d(v)=d⁺(v)+d^-(v).

Учитывая, что каждая дуга положительно инцидентна одной вершине и отрицательно инцидентна также одной вершине, получим

,

где |A| означает число дуг графа. Напомним, что в неориентированном случае мы имеем

.

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

Ориентированным маршрутом (ормаршрутом) длины n является последовательность (не обязательно различных) дуг а₁, а₂, …, а_n таких, что для соответствующей последовательности n+1 вершин v₀, v₁, …, v _n справедливо а_i@(v_i-1, v_i) для i=1, 2, …, n. Например, на рис. 2.2 последовательность а₁, а₅, а₅, а₃ образует ориентированный маршрут длины 4 (соответствующая последовательность вершин v₃, v₂, v₂, v₂, v₁). Ориентированный маршрут называется замкнутым, если v₀=v _n и незамкнутым, если v₀¹v _n. В последнем случае говорят, что ориентированный маршрут соединяет v₀ и v _n или, точнее, что он идет из v₀ в v _n.

Очевидно, незамкнутый (замкнутый) ориентированный маршрут в ориентированном графе определяет соответствующий незамкнутый (замкнутый) маршрут в соответствующем неориентированном графе. Однако, обратное, вообще говоря, неверно.

Например, на рис 6.2 последовательность а1, а2, а6 определяет незамкнутый маршрут, соединяющий вершины v2 и v4, но из-за различной ориентации дуг не образует ориентированный маршрут. Ориентированный маршрут, в котором нет повторяющихся дуг, называется путем или контуром (ориентированным циклом) в зависимости от того, является ли он замкнутым или нет. Соответствующее множество дуг, без учета упорядоченности, называется неупорядоченным путем или неупорядоченным контуром соответственно.

Рис. 6.2 - Ормаршруты, пути и контуры

Если вершины v₀, v₁, …, v _n различны (в этом случае дуги также различны), то путь или контур, так же как и соответствующие неупорядоченные пути и контуры, называется простым. Ориентированный граф называется циклическим, контурным, если он содержит, по крайней мере, один контур, и ациклическим (бесконтурным) в противном случае. (Заметим, что петля является специальным видом контура.)