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

UptoLike

ВУЗ: 

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

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

Рубрика: 

21
u
1
v
L
k
v
u
1
v
L
k
v
Рис. 16
u
1
v
L
k
v
2
v
u
1
v
L
k
v
1k
v
Рис. 17
Определение 5.14. Цикл, содержащий каждую дугу оргра-
фа, называется эйлеровым циклом.
Определение 5.15. Орграф называется связным, если от лю-
бой его вершины до любой другой можно перейти по дугам без
учета их ориентации.
Определение 5.16. Связный орграф называется эйлеровым
орграфом, если в нем есть эйлеров цикл.
Теорема 5.3. Связный орграф является эйлеровым тогда и
только тогда, когда для каждой его вершины
v
выполняется
равенство
vdvd
.
Д о к а з а т е л ь с т в о. Теорема доказывается точно так же,
как теорема 2.1.
Теорема 5.4. Связный орграф
G
эйлеров тогда и только
тогда, когда
G
является объединением контуров, попарно не
имеющих общих ребер.
Д о к а з а т е л ь с т в о. Необходимость. Пусть
G
– эйле-
ров орграф. Рассмотрим его любую вершину
1
u . Выйдем из
вершины
1
u по некоторой дуге
21
,uu . Это возможно сделать,
так как орграф
G
связный. Поскольку
22
udud
, то из
вершины
2
u можно выйти по дуге
32
,uu . Орграф
G
имеет
конечное число вершин, поэтому в конце концов мы попадем в
некоторую вершину
w
, в которой были раньше. Часть цепи,

Страницы