Путем в орграфе называется последовательность дуг, в которой конечная вершина всякой дуги, кроме последней, является начальной вершиной следующей дуги.
Например, для графа на рис. 8.1 последовательности дуг
M1: a6, a5, a9, a8, a4 ,
M2: a1, a6, a5, a9, a7 ,
M3: a1, a6, a5, a9, a10, a6, a4
являются путями. Пути могут быть различными.
Рис. 8.1. Орграф
Орцепью (или простым путем) называется такой путь, в котором каждая дуга используется не более одного раза.
Так пути M1 и M2 являются орцепями, а M3 нет, поскольку дуга a6 используется дважды.
Простой орцепью (или элементарным путем) называется путь, в котором каждая вершина используется не более одного раза.
Простой орцепью является путь M2 .
Для неориентированного графа понятия маршрута, цепи и простой цепи аналогичны понятиям пути, орцепи и простой орцепи в орграфе. (В определениях следует заменить слово "дуга" на слово "ребро").
Путь или маршрут можно изображать также последовательностью вершин. Так путь M1 можно представить последователь-ностью вершин х2, х5, х4, х3, х5, х6 , и такое представление часто оказывается более полезным.