Дискретная математика: графы и автоматы. Альпин Ю.А - 11 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

§ 2. Эйлеровы и гамильтоновы графы 11
жды по одному ребру. Поскольку число рёбер конечно, построение
закончится попаданием в такую вершину v
0
, что все инцидентные ей
рёбра уже пройдены. Докажем, что v
0
= v, следовательно, построен
цикл. Предположим, что v
0
6= v, тогда выходит, что наш маршрут
несколько раз прошёл через вершину v
0
, используя по два инцидент-
ных ей ребра, и на последнем шаге вошел в неё по последнему сво-
бодному ребру. Получается, что степень вершины v
0
— нечётное чис-
ло, но это противоречит условию теоремы. Итак, построен некоторый
цикл C
1
. Заметим, что при этом связность графа не потребовалась.
Если C
1
содержит все рёбра графа, то этот цикл эйлеров. Если не
все, то существует некоторая вершина u цикла C
1
, инцидентная реб-
ру, не входящему в C
1
. В противном случае подграф, порождённый
рёбрами, не входящими в C
1
, не имел бы с C
1
общих вершин. Но это
противоречит связности графа.
Согласно рассуждению в части необходимости, каждая вершина
цикла инцидентна чётному числу рёбер этого цикла. Отсюда и из
условия теоремы следует, что рёбер, инцидентных любой из вершин
графа и притом не принадлежащих C
1
, тоже чётное число. Поэтому
можно построить новый цикл C
2
, начиная с вершины u по сказанно-
му выше правилу, но не пользуясь рёбрами C
1
. Соединяя C
1
и C
2
в
вершине u, как показано на рисунке 4, получим цикл C
0
.
Рис. 4
Если он содержит все рёбра графа, то построение закончено. Если нет,
то найдётся вершина s ∈ C
0
, инцидентная ребру не из C
0
. Сделаем её
началом нового цикла C
3
и так далее. Ясно, что на некотором шаге
будет получен цикл, содержащий все рёбра графа, то есть, эйлеров
цикл. ¤
Упражнение 1. Решите задачу о кёнигсбергских мостах.
Незамкнутую цепь назовём эйлеровой, если она содержит все рёб-
ра графа. Вопрос о существовании такой цепи легко решается с по-
мощью теоремы 1.
Следствие 1. Незамкнутая эйлерова цепь в связном графе су-
ществует тогда и только тогда, когда граф содержит ровно две
вершины нечётной степени.
Д о к а з а т е л ь с т в о. Пусть эйлерова цепь существует. Соеди-
§ 2. Эйлеровы и гамильтоновы графы                                   11


жды по одному ребру. Поскольку число рёбер конечно, построение
закончится попаданием в такую вершину v 0 , что все инцидентные ей
рёбра уже пройдены. Докажем, что v 0 = v, следовательно, построен
цикл. Предположим, что v 0 6= v, тогда выходит, что наш маршрут
несколько раз прошёл через вершину v 0 , используя по два инцидент-
ных ей ребра, и на последнем шаге вошел в неё по последнему сво-
бодному ребру. Получается, что степень вершины v 0 — нечётное чис-
ло, но это противоречит условию теоремы. Итак, построен некоторый
цикл C1 . Заметим, что при этом связность графа не потребовалась.
Если C1 содержит все рёбра графа, то этот цикл эйлеров. Если не
все, то существует некоторая вершина u цикла C1 , инцидентная реб-
ру, не входящему в C1 . В противном случае подграф, порождённый
рёбрами, не входящими в C1 , не имел бы с C1 общих вершин. Но это
противоречит связности графа.
    Согласно рассуждению в части необходимости, каждая вершина
цикла инцидентна чётному числу рёбер этого цикла. Отсюда и из
условия теоремы следует, что рёбер, инцидентных любой из вершин
графа и притом не принадлежащих C1 , тоже чётное число. Поэтому
можно построить новый цикл C2 , начиная с вершины u по сказанно-
му выше правилу, но не пользуясь рёбрами C1 . Соединяя C1 и C2 в
вершине u, как показано на рисунке 4, получим цикл C 0 .




                                 Рис. 4

Если он содержит все рёбра графа, то построение закончено. Если нет,
то найдётся вершина s ∈ C 0 , инцидентная ребру не из C 0 . Сделаем её
началом нового цикла C3 и так далее. Ясно, что на некотором шаге
будет получен цикл, содержащий все рёбра графа, то есть, эйлеров
цикл. ¤
    Упражнение 1. Решите задачу о кёнигсбергских мостах.
    Незамкнутую цепь назовём эйлеровой, если она содержит все рёб-
ра графа. Вопрос о существовании такой цепи легко решается с по-
мощью теоремы 1.
    Следствие 1. Незамкнутая эйлерова цепь в связном графе су-
ществует тогда и только тогда, когда граф содержит ровно две
вершины нечётной степени.
    Д о к а з а т е л ь с т в о. Пусть эйлерова цепь существует. Соеди-

Страницы