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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

=
случае.противномв,0
;цикл й в входит ребро еесли,1 i-j-
c
ji
Множество C(G) всех векторов, каждый из которых соответствует одному
циклу графа G, образует векторное пространство, называемое пространством циклов графа G. При
этом для любых двух циклов R
i
,
R
j
∈ C(G), R
i
∩ R
j
≠ ∅, существует некоторый третий цикл (R
i
⊕ R
j
) ∈ C(G), где символ ⊕ обозначает
поразрядное сложение по модулю два.
Базисом пространства циклов называется всякая система линейно незави-
симых векторов, порождающая данное пространство. Всякий элемент пространства циклов единствен-
ным образом представим в виде линейной комбинации векторов базиса пространства циклов. Если про-
странство имеет базис из n векторов, то оно называется n-мерным пространством.
Базис циклов графа G – это базис пространства циклов графа G, состоящий
из простых циклов. Любой вектор пространства циклов графа G можно представить в виде линейной
комбинации векторов базиса циклов.
Рассмотрим граф, изображенный на рис. 21, а. Цикломатическая матрица
C(G) этого графа имеет вид:
a b c d e f m g h
0 1 1 0 0 0 0 1 1 R
1
1 0 0 0 0 1 1 1 0 R
2
C(G)
=
1 0 0 1 1 1 0 1 1 R
3
0 1 1 1 1 0 1 1 0 R
4
1 1 1 0 0 1 1 0 1 R
5
0 0 0 1 1 0 1 0 1 R
6
1 1 1 1 1 1 0 0 0 R
7
В качестве базиса циклов можно взять множество циклов {R
1
, R
2
, R
3
}. Мож-
но убедиться в том, что все остальные циклы выражаются их линейными комбинациями:
R
1
⊕ R
2
⊕ R
3
= R
4
, R
1
⊕ R
2
= R
5
, R
1
⊕ R
3
= R
7
, R
2
⊕ R
3
= R
6
.
Деревом называется связный граф, не содержащий ни одного цикла. Остов-
ный подграф графа – это подграф, содержащий все вершины графа. Остовом называется остовный под-
граф, являющийся деревом. Хордой остова D в связном графе G называется всякое ребро графа, не
принадлежащее D. Любой подграф, который состоит из хорды и остова, имеет точно один цикл.
Цикломатическое число ν(G) графа G равно числу хорд любого остова гра-
фа G. Если связный граф G имеет n вершин и m ребер, то его цикломатическое число
ν(G) = m – n + 1.
Если граф G содержит k компонент связности, n вершин и m ребер, то
ν(G) = m – n + k.
a b
c
d
e
f
m
g
h
a b
e
f
g
h
а)
б)
Рис.

Страницы