Пути и маршруты

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

Например, для графа на рис. 8.1 последовательности дуг

M₁: a₆, a₅, a₉, a₈, a₄,

M₂: a₁, a₆, a₅, a₉, a₇,

M₃: a₁, a₆, a₅, a₉, a₁₀, a₆, a₄

являются путями. Пути могут быть различными.

Рис. 8.1. Орграф

Орцепью (или простым путем) называется такой путь, в котором каждая дуга используется не более одного раза.

Так пути M₁ и M₂ являются орцепями, а M₃ нет, поскольку дуга a₆ используется дважды.

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

Простой орцепью является путь M₂.

Для неориентированного графа понятия маршрута, цепи и простой цепи аналогичны понятиям пути, орцепи и простой орцепи в орграфе. (В определениях следует заменить слово "дуга" на слово "ребро").

Путь или маршрут можно изображать также последовательностью вершин. Так путь M₁ можно представить последователь-ностью вершин х₂, х₅, х₄, х₃, х₅, х₆, и такое представление часто оказывается более полезным.