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

Определение. Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.

В случае простого графа маршрут однозначно определяется последовательностью вершин или последовательностью ребер. Если маршрут в простом графе задан последовательностью вершин v₀, v₁,, … , v_k, то вершины v₀, v_k называют концами маршрута. Если v₀ = v_k, то маршрут называют замкнутым, в противном случае – незамкнутым.

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

Определение. Простой цикл с р вершинами обозначается С_р . Например, граф – это одновременно граф С₃.

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

Рассмотрим граф на рис. 11. Маршруты в этом графе будем задавать последовательностью вершин.

Пример маршрута: 1 – 2 – 3 – 5 – 7 – 4 – 3 – 5 – 6 – 2 – 3 – 4.

Пример замкнутого маршрута: 3 – 4 – 5 – 7 – 3 – 4 – 1 – 3.

Пример цепи, соединяющий вершины 6 и 8: 6 – 5 – 3 – 4 – 5 – 7 – 3 – 2 – 6 – 8.

Пример цикла: 5 – 3 – 2 – 6 – 5 – 7 – 4 – 5.

Примеры простых цепей, соединяющих вершины 1 и 6: 1 – 3 – 4 – 5 – 6; 1 – 2 – 6; 1 – 4 – 7 – 8 – 6.

Примеры простых циклов: 3 – 5 – 7 – 4 – 3; 1 – 2 – 6 – 8 – 7 – 4 – 1;

1 – 2 – 6 – 5 – 7 – 3 – 1.

Рис. 11

Рассмотрим ориентированный граф на рис. 12. Ориентированные маршруты в этом графе будем задавать последовательностью вершин, проходимых в направлении ориентации дуг.

Рис. 12

Пример ориентированного маршрута: 1 ® 2 ® 3 ® 5 ® 2 ® 6 ® 8 ® 5.

Пример замкнутого ориентированного маршрута: 1 ® 4 ® 5 ® 2 ® 6 ® 8 ® 5 ® 2 ® 3 ® 1.

Пример ориентированной цепи: 4 ® 5 ® 7 ® 8 ®5 ® 2.

Пример замкнутой ориентированной цепи:6 ® 8 ® 5 ® 2 ® 3 ® 1 ® 5 ® 6.

Пример пути, соединяющего вершины 3 и 9: 3 ® 1 ® 4 ® 5® 6 ® 9.

Пример контура:5 ® 7 ® 4 ® 5.