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

Определение 7.1. Пусть G = (S, U) – граф (орграф). Чередующаяся последовательность его вершин и рëбер (дуг)

x₁, u₁, x₂, u₂, …, x_k, u_k, x_k+1 (7.1)

(где k ³ 1, x_i Î S, i = 1, …, k +1, u_j Î U, j = 1, …, k) такая, что для каждого

j = 1, …, k ребро (дуга) u_j имеет вид (x_j, x_j+1), называется маршрутом, соединяющим вершины x₁ и x_k+1 (путëм из вершины x₁ в вершину x_k+1). При этом вершина x₁ называется начальной, а вершина x_k+1 – конечной.

Очевидно, что маршрут можно задать последовательностью его вершин

x₁, x₂, …, x_k+1 или последовательностью ребер u₁, u₂, …, u_k.

Определение 7.2. Длиной маршрута (пути) называется число рëбер (дуг) в маршруте (пути).

Определение 7.3. Маршрут (путь) называется замкнутым, если его начальная и конечная вершины совпадают (т.е. x₁ = x_k+1).

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

Определение 7.5. Простой цепью называется цепь, в которой все вершины попарно различны.

Определение 7.6. Циклом (контуром) называется замкнутый маршрут (путь), в котором все рëбра (дуги) попарно различны.

Определение 7.7. Простым циклом (контуром) называется цикл(контур), в котором все вершины попарно различны.

Пример 7.1. Рассмотрим граф на рис. 12. Привести пример (незамкнутого) маршрута, замкнутого маршрута, цепи (не являющейся простой), простой цепи, цикла (не являющегося простым), простого цикла.

Решение. Пример (незамкнутого) маршрута: x₁ - x₇ - x₃ - x₄ - x₆ - x₉ - x₈.

Пример замкнутого маршрута:

x₁ - x₂ - x₆ - x₅ - x₄ - x ₆ - x₇ - x₁.

Пример цепи (не являющейся простой):

x₉ - x₆ - x₂ - x₁ - x₇ - x₆ - x₄.

Пример простой цепи:

x₈ - x₇ - x₃ - x₄ - x₅ - x₆ - x₂.

Пример цикла (не являющегося простым):

x₁ - x₂ - x₆ - x₉ - x₄ - x₆ - x₇ - x₁.

Пример простого цикла:

x₇ - x₃ - x₄ - x₆ - x₉ - x₈ - x₇.