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

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

Рис. 2.2.

Ориентированный маршрут называется замкнутым, если и незамкнутым, если последнем случае говорят, что ориентированный маршрут соединяет или, точнее, что он идет из

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

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

Упражнения

(см. скан)