Математическое моделирование на графах. Часть 1. Берцун В.Н. - 13 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Глава 1. Основные понятия теории графов 13
Циклом называется замкнутая цепь, в которой совпадают ее на-
чальная и конечная вершины. Простым циклом в графе называется
простая замкнутая цепь. На рис. 1.12 x
2
, x
3
, x
4
, x
6
, x
5
, x
4
, x
2
– цикл, x
2
,
x
3
, x
4
, x
2
– простой цикл. Очевидно, что в простом цикле с n верши-
нами (n ≥ 3), который будем обозначать С
n
, содержится n рёбер. На
рис.1.13 представлены простые циклы: С
3
, С
5
, С
6
. Длина цикла изме-
ряется числом рёбер в этом цикле.
C
A
B
C
B
E
D
F
A
A
DB
C
E
Рис. 1.13
В простой цепи число вершин на единицу больше, чем число ре-
бер, а в простом цикле их количество совпадает.
Для графа G на рис. 1.14 все циклы длины 4: (AB, BC, CD, DA),
(AE, ED, DC, CA), (AD, DE, EB, BA), (AC, CB, BE, EA), являются про-
стыми.
A
B
C
DE
Рис. 1.14
Утверждение 1.3. В графе G любой цикл содержит простой цикл.

Страницы