ВУЗ:
Составители:
Рубрика:
4
Д о к а з а т е л ь с т в о. Пусть существует путь:
0
vv ,
ee ,...,
1
, uv
. Рассмотрим все пути из
v
в
u
, состоящие из
рёбер, входящих в этот путь. Среди них выберем самый корот-
кий:
0
vv , uvevve
kkk
,,,...,,
111
. Покажем, что
jivv
ji
.
Пусть
ji
vv
, тогда путь uvvevevv
kjji
,...,,,,...,,
1110
име-
ет длину
kijk . Противоречие с предположением о ми-
нимальности пути.
Определение 1.15. Путь (1) называется замкнутым, если
n
vv
0
.
Определение 1.16. Замкнутая цепь называется циклом.
Определение 1.17. Простая замкнутая цепь называется про-
стым циклом (
n
vv
0
и вершины не повторяются).
Теорема 1.5. Если существует замкнутый простой путь,
то из его рёбер можно составить цикл.
Д о к а з а т е л ь с т в о теоремы аналогично доказательству
теоремы 1.4.
Замечание к теореме 1.5. Требование простоты пути в тео-
реме 1.5 существенно: рассмотрим путь
010
,,,, vevev . Из ребра
e
цикл построить нельзя.
Теорема 1.6. Пусть EVG , – граф, все вершины кото-
рого имеют чётную степень. Тогда для любого ребра сущест-
вует замкнутый простой путь, содержащий это ребро.
Д о к а з а т е л ь с т в о. Рассмотрим произвольное ребро
101
,vve . По предположению теоремы
1
deg v – чётное чис-
ло. Тогда существует ребро
212
,vve , отличное от
1
e . В силу
чётности
2
deg v найдётся ребро
323
,vve и т.д. Так как
множество вершин
V
конечно и каждый раз берётся новое не-
использованное ребро, инцидентное
i
v , то в конце концов снова
придём в вершину
0
v .
Определение 1.18. Две вершины называются связными, ес-
ли существует путь, соединяющий их.
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
