ВУЗ:
Составители:
Рубрика:
58
Например, на рис. 23, а изображён связный граф G, в качестве осто-
ва которого может выступать дерево, представленное на рис. 23, б. При
этом хордами остова D(G) являются рёбра c, d и m.
Цикломатическим числом ν(G) графа G называется число хорд лю-
бого остова графа G. Если граф G, имеющий p вершин и q рёбер, связен,
то его цикломатическое число ν(G) определяется выражением
ν(G) = q – p + 1.
Если граф G содержит k компонент связности, то его цикломатиче-
ское число ν(G) можно вычислить по более общей формуле
ν(G) = q – p + k.
Цикломатическое число графа G, состоящего из k компонент связ-
ности G
1
, G
2
, ..., G
k
, может быть определено как сумма цикломатических
чисел этих компонент:
ν(G) =
∑
=
ν
k
i
i
G
1
)(
.
Заметим, что цикломатическое число ν(G) выбранного в качестве
примера связного графа G (рис. 23, а), имеющего девять рёбер и семь
вершин, равно трём.
Теорема (Эйлера). Число базисных циклов графа G постоянно и
равно его цикломатическому числу ν(G). ■
Матрица, представляющая базис циклов графа G относительно не-
которого остова D(G), называется базисной цикломатической матрицей
B(G). При этом каждый из ν(G) базисных циклов матрицы B(G) образует-
ся некоторой хордой и соответствующими ей рёбрами остова D(G).
В нашем случае базисная цикломатическая матрица B(G) графа G
(рис. 23, а) относительно остова D(G) (рис. 23, б) будет содержать три ба-
зисных цикла:
a b
c
d
e
f
m
g
h
a b
e
f
g
h
а)
б)
Рис. 23
Страницы
- « первая
- ‹ предыдущая
- …
- 56
- 57
- 58
- 59
- 60
- …
- следующая ›
- последняя »
