Дискретная математика. Кулаков Ю.В - 43 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Цикломатическое число несвязного графа G с k компонентами связности G
i
, i = 1, 2, ..., k может быть
определено и как сумма цикломатических чисел его компонент связности:
ν(G) =
∑
=
ν
k
i
i
G
1
)( .
Лесом называется граф, не содержащий циклов. Если лес G имеет n вершин
и k компонент связности, то он содержит (n – k) ребер.
Теорема (теорема Эйлера). Число базисных циклов графа постоянно и рав-
но его цикломатическому числу.
Базисом циклов для данного остовного леса D графа G является множество
всех циклов графа G, каждый из которых содержит только одну хорду остова D. В рассматриваемом приме-
ре множество циклов {R
1
, R
2
, R
3
} является базисом циклов графа G относительно остова D, представлен-
ного на рис. 21, б.
Цикломатическая матрица, представляющая базис циклов графа G, называ-
ется базисной цикломатической матрицей C
б
(G). В нашем случае базисная цикломатическая матрица
имеет следующий вид:
хорды остов D
c m d a b e f g h
1 0 0 0 1 0 0 1 1 R
1
C
б
(G)
=
0 1 0 1 0 0 1 1 0 R
2
0 0 1 1 0 1 1 1 1 R
3
Выполнив (2
ν
– ν – 1) раз операцию сложения по модулю два над базисными
циклами, можно получить все множество циклов этого пространства.
Изучая свойства циклов графа, можно определить принадлежность графа к
определенному классу, например, к классу двудольных графов.
Теорема. Граф является двудольным тогда и только тогда, когда все его
циклы имеют четную длину (четны).
Если в двудольном графе каждая вершина из одного множества вершин V
1
соединена с каждой вершиной из другого множества вершин V
2
, то граф называется полным двудольным
графом и обозначается K
m,n
, где m – число вершин V
1
, а n – число вершин V
2
. Граф K
m,n
имеет (m + n)
вершин и mn ребер. Полный двудольный граф K
1,n
называется звездным графом (звездой) и является де-
ревом. Заметим, что любое дерево является двудольным графом.
Задачи и упражнения
1 Определить цикломатическое число ν(G) графа G:
2 Получить базисную цикломатическую матрицу C
б
(G) графа G (см. задачу 1, а) относительно ос-
това:
a
b
c
d
e
f
g
h
а)
a
b
c
d
e
f
g
б)
a
b
c
d
e
f
в)
a
b
c
d
e
f
г)
g
; ;
.
;

Страницы