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

Ответы и пояснения

1. Пусть маршрут, соединяющий вершины Л и В, не является простой цепью. Тогда он проходит не менее двух раз через некоторую вершину С, т.е. внутри маршрута содержатся один или несколько замкнутых маршрутов с вершиной в точке С. Удаляя ребра этих замкнутых маршрутов, мы получим новый маршрут, который содержится в исходном, соединяет А и В и через вершину С проходит всего один раз (см. пример на рис. 24). Осуществляя подобную процедуру необходимое число раз, получим искомую простую цепь.

Рис. 24

Следствия. 1) Если незамкнутый маршрут не является простым, то он содержит внутри себя замкнутый маршрут; 2) Внутри цепи, соединяющей вершины А и В, содержится простая цепь, соединяющая эти вершины; 3) Внутри непростой цепи содержится цикл.

2. Упражнение доказывается по аналогии с упражнением 1.

Следствия. 1) Внутри непростого цикла содержится другой цикл; 2) Любой непростой цикл можно разбить па конечное число простых циклов.

Рис. 25

3. Нельзя. Рассмотрим,

например, последовательность ребер а,,а2,Оз, представленных на рис. 25. Ребра этой последовательности являются попарно смежными, но не образуют маршрут.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

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