Элементы теории графов. Сюсюкалов А.И - 16 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

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

Рубрика: 

11
Д о к а з а т е л ь с т в о. Обозначим вершины
k
vvv ,...,,
21
,
kkk
vvv
221
,...,,
. Добавим
k
рёбер
11
,
k
vv ,
22
,
k
vv , …,
kk
vv
2
, , тогда в новом графе найдётся эйлеров цикл
P
. При
удалении рёбер
iki
vv
,
ki ,1 граф распадётся на
k
цепей,
содержащих все рёбра.
Теорема 2.4. Связный граф является эйлеровым тогда и
только тогда, когда его рёбра можно разбить на непересе-
кающиеся простые циклы.
Д о к а з а т е л ь с т в о. Необходимость. Пусть
G
– эйле-
ров граф. Начнём проходить эйлеров
цикл графа, начиная с любой вер-
шины
1
v , до тех пор, пока не попа-
дём в вершину
w
, в которой уже
были (см. рис. 8).
Часть эйлерова цикла от вершины
w
до вершины
w
обра-
зует простой цикл
1
С .
Удалим из графа
G
рёбра цикла
1
С . В полученном графе
2
G все вершины имеют чётную степень, следовательно, все его
компоненты будут эйлеровыми графами. Так же как и ранее,
выделим в
2
G цикл
2
С . Указанный процесс будем продолжать,
пока не разобьём все рёбра графа на простые циклы.
Достаточность. Пусть рёбра графа разбиты на простые
циклы. Объединим их в эйлеров цикл, как это делали при дока-
зательстве достаточности в теореме 2.1. Теорема доказана.

Страницы