Дискретная математика. Громов Ю.Ю - 71 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

71
незамкнутая цепь, в которую каждое ребро графа входит ровно один раз.
Граф G, который не является эйлеровым и не является полуэйлеровым
графом, будем называть неэйлеровым графом.
Для иллюстрации на рис. 34, а, б и в изображены соответственно не-
эйлеров, полуэйлеров и эйлеров графы.
Заметим, что первая работа о графах принадлежит швейцарскому
математику Леонарду Эйлеру (1707 − 1783). Она появилась в 1736 г. в
публикациях Петербургской Академии наук. Эйлер начал её с рассмот-
рения одной головоломки − так называемой «задачи о кёнигсбергских
мостах». Вопрос заключался в том, можно ли, совершая прогулку по го-
роду, выйти из дома и вернуться обратно, пройдя в точности один раз по
каждому мосту (рис. 35).
Эйлер обобщил постановку задачи и нашёл критерий существова-
ния такого маршрута.
Теорема. Для связного графа G следующие утверждения эквива-
лентны: G − эйлеров граф; каждая вершина графа G имеет чётную сте-
пень; множество рёбер графа G можно разбить на простые циклы. ■
Например, каждая вершина эйлерова графа на рис. 34, в имеет
чётную степень, а множество его рёбер {a, b, c, d, e, f, g, h, k, m, p, s}
можно разбить на подмножества, определяющие простые циклы (a, b, c, d),
(e, h, s, p) и (f, k, m, g).
Граф на рис. 36, представляющий схему кёнигсбергских мостов, со-
держит вершины нечётной степени и, в соответствии с теоремой, не яв-
ляется эйлеровым графом. Таким образом, упомянутую выше прогулку
по мостам совершить нельзя.
Рис. 35
Рис. 36
а)
б)
в)
Рис. 34
a
b
c
d
e
f
g
h
a
b
c
d
e
f
g
h
k
m
a
b
c
d
e
f
g
h
k
m
p
s

Страницы