Маршруты, цепи и циклы

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

, (1)

, (2)

(3)

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

°

°

°

°

°

°

Рис. 1.

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

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

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

Аналогично тому, как мы определили орцепи и простые цепи, можно определить цепи и простые цепи.

Путь или маршрут можно изображать также последовательностью вершин. Например, путь (1) можно записать в виде: .

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