Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Цепи и циклы

Цепью называется незамкнутый маршрут, состоящий из последовательности различных ребер. Замкнутый маршрут, состоящий из последовательности различных ребер, называется циклом. Так, маршрут д,,я45, д62 на рис. 23 является цепью, а замкнутый маршрут д7645 представляет собой цикл. Заметим, что маршрут ахАьь22 не является цепью, а замкнутый маршрут а1ьАь2 не является циклом.

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

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

Упражнения

  • 1. Докажите, что любой незамкнутый маршрут, соединяющий вершины А и В, содержит в себе простую цепь, соединяющую эти вершины.
  • 2. Докажите, что внутри любого замкнутого маршрута, не являющегося простым циклом, содержится другой замкнутый маршрут.
  • 3. Можно ли определить маршрут как последовательность ребер, удовлетворяющих условию: «любая пара ребер, соседних в этой последовательности, является смежной»?
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы