Путь, ориентированный маршрут

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

Пример. На рис. 2 последовательности дуг

а₆, a₅, a₉, a₈, a₄ (1.1)

a₁, a₆, a₅, a₉ (1.2)

a₁, a₆, a₅, a₉, a₁₀, a₆, a₄ (1.3)

являются путями.

Путем в графе G = <V, E> назовем последовательность вершин v ₀, v ₁,..., v _k такую что k ≥ 0 п v_i - v_i+1 (или и v_i → v_i+1, если граф G — ориентированный), i = 0,..., k - 1. Термин «путь» в теории графов используется только в отношении орграфов, для графов используются термины «цепь» или «маршрут». Вершины v ₀ и v _k будем называть соответственно началом и концом пути, а число k — длиной пути. Путь, начало и конец которого совпадают, будем называть циклом. Введенный так термин «цикл» в теории графов используется только в отношении графов, для орграфов используется термин «контур».

Если все вершины пути v ₀, v ₁,..., v _k различны, то будем говорить об элементарном пути. Соответственно цикл v ₁,..., v _k (v ₁ = v _k ) будем называть элементарным, если вершины v ₁,..., v _k различны.

Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер , в которой каждое ребро , за исключением, возможно, первого и последнего ребер, связано с ребрами и своими двумя концевыми вершинами.

Пример.

Последовательности дуг

(1.4)

(1.5)

(1.6)

в графе, изображенном на рис. 2, являются маршрутами; черта над символом дуги означает, что ее ориентацией пренебрегают, т. е. дуга рассматривается как неориентированное ребро.