Маршруты. Цепи. Циклы

Пусть задан граф G(V, E). Последовательность вершин и ребер V₀ , l_{1 ,,} V₁ , …, l, V, в которой каждые два соседних элемента инцидентны, называется маршрутом.

Замечание: маршрут может быть задан последовательностью вершин: V, V,V,…,V. Вершины Vи V─ концы маршрута.

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

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

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

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

Граф, не имеющий циклов, называется ациклическим.

Задача. Выделить маршрут, связывающий V , V , цепь, простую цепь, цикл, простой цикл : рис.33.

Рис. 33. Маршруты, цепи, циклы

Решение:

V, l, V, l, V, l, V, l, V─ маршрут, но не цепь.

V, V, V, V, V─ цепь.

V, V, V, V─ простая цепь.

V, V, V, V, V, V─ цикл.

V, V, V, V─ простой цикл.

Теорема. Если существует цепь, соединяющая две вершины, то существует и простая цепь, соединяющая эти вершины..

Доказательство:

Пусть существует цепь V,V,…,V,V,…,V,…,V. Все вершины и ребра, расположенные между Vи вторым вхождением V, можно из цепи выбросить вместе с одной из V. Получилась новая цепь, содержащая Vодин раз. Если в ней еще есть одинаковые вершины, поступаем так же. Получится цепь, не содержащая одинаковых вершин, то есть простая цепь.

Что и требовалось доказать.

Замечание: в орграфах цепь называется путем, а цикл - контуром.