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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
Так как
G
связен, то в
P
найдётся вершина
*
v
, инцидент-
ная рёбрам из
P
. Из
*
v
можно построить новую цепь
P
из
рёбер
P
. Такая цепь может закончиться только в
*
v
. Из
P
и
P
составим новый цикл
0
**
01
,, vvPPvvPP
(рис. 6).
Если цикл
1
P не является эйлеровым, то это построение по-
вторяется. В силу конечности графа этот процесс завершится
построением эйлерова цикла. Теорема доказана.
Теорема 2.2. Для того чтобы в связном графе
G
имелась
цепь
*
0
,vvP , содержащая все его рёбра по одному разу, необ-
ходимо и достаточно, чтобы
*
0
,vv
были единственными вершинами не-
чётной степени.
Для доказательства достаточно до-
бавить к графу
G
новое ребро
*
0
,vv ,
и все его вершины станут чётными. Новый граф обладает эйле-
ровым циклом
P
. После удаления
*
0
,vv получим цепь
*
0
,vvP (рис. 7).
Следствие. Если в графе больше двух нечётных вершин, то
его правильный обход (без повторения рёбер) невозможен.
Теорема 2.3. В связном графе с
k2
нечётными вершинами
имеется семейство из
k
цепей, которые в совокупности со-
держат все рёбра графа по одному разу.

Страницы