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

UptoLike

ВУЗ: 

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

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

Рубрика: 

9
12. Каждый из учеников 9 «а» класса дружит ровно с тремя
учениками 9 «б» класса, а каждый ученик 9 «б» класса дружит
ровно с тремя учениками 9 «а» класса. Докажите, что число уче-
ников в этих классах одинаково.
13. Можно ли так нарисовать 5 горизонтальных и 4 верти-
кальных отрезка, чтобы каждый горизонтальный отрезок пере-
секался ровно с тремя вертикальными, а каждый вертикальный
ровно с тремя горизонтальными?
2. ЭЙЛЕРОВЫ ГРАФЫ
2.1. Определения и свойства
Определение. Если граф имеет цикл, содержащий все рёб-
ра, то он называется эйлеровым графом, а цикл называется эй-
леровым циклом.
Теорема 2.1. Для того чтобы граф
G
был эйлеровым, не-
обходимо и достаточно, чтобы он был: 1) связен; 2) все его
степени вершин были чётными.
Д о к а з а т е л ь с т в о. Необходимость. Связность следует
из определения эйлерова цикла, поэтому условие 1 необходимо.
Когда эйлеров цикл проходит через вершину, он должен войти в
неё по одному ребру и выйти по другому, поэтому условие 2
также необходимо.
Достаточность. Пусть условия 1 и 2 выполнены. Начнём
цепь
P
в вершине
0
v и будем продолжать её через разные рёб-
ра, пока этот процесс не закончится в
0
v , в силу конечности
графа
G
и того, что
0
v и другие вершины имеют чётную сте-
пень. Если
P
содержит не все рёбра
G
, то удалим из
G
цепь
P
, состоящую из рёбер этого цикла.
Графы
G
и
P
имеют вершины с чётными степенями, по-
этому оставшийся граф
P
(после удаления из
G
цепи
P
) так-
же имеет чётные вершины.

Страницы