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

Пусть задан граф 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 один раз. Если в ней еще есть одинаковые вершины, поступаем так же. Получится цепь, не содержащая одинаковых вершин, то есть простая цепь.

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

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

Дата добавления: 2014-01-06