Маршруты. Цепи. Циклы
Пусть задан граф G(V, E). Последовательность вершин и ребер V0 , l1 ,, V1 , …, 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один раз. Если в ней еще есть одинаковые вершины, поступаем так же. Получится цепь, не содержащая одинаковых вершин, то есть простая цепь.
Что и требовалось доказать.
Замечание: в орграфах цепь называется путем, а цикл - контуром.