Цепи и циклы

Цепью называется незамкнутый маршрут, состоящий из последовательности различных ребер. Замкнутый маршрут, состоящий из последовательности различных ребер, называется циклом. Так, маршрут д,,я₄,а₅, д₆,я₂ на рис. 23 является цепью, а замкнутый маршрут д₇,а₆,д₄,д₅ представляет собой цикл. Заметим, что маршрут а_х,а_А,а_ь,а_ь,а₂,а₂ не является цепью, а замкнутый маршрут а₁,а_ь,а_А,а_ь,а₂ не является циклом.

Простые цепи и циклы

Частным случаем цепей являются такие маршруты, которые не проходят дважды через одну и ту же вершину. Такие маршруты называются простыми цепями. Ясно, что если маршрут не проходит дважды через одну и ту же вершину, то он не проходит дважды и через одно и то же ребро. Простым циклом называется маршрут, в котором начальная и конечная вершины совпадают, а все остальные вершины различны. Очевидно, что не всякий цикл является простым.

Упражнения

• 1. Докажите, что любой незамкнутый маршрут, соединяющий вершины А и В, содержит в себе простую цепь, соединяющую эти вершины.
• 2. Докажите, что внутри любого замкнутого маршрута, не являющегося простым циклом, содержится другой замкнутый маршрут.
• 3. Можно ли определить маршрут как последовательность ребер, удовлетворяющих условию: «любая пара ребер, соседних в этой последовательности, является смежной»?