Дискретная математика. Громов Ю.Ю - 57 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

57
4. Определить диаметр d(G), матрицу достижимости D(G), число
компонент сильной связности k(G) и множества вершин, образующих
компоненты сильной связности ориентированного графа G:
10. ЦИКЛОМАТИКА
Множество C(G) всех циклов графа G образует пространство, назы-
ваемое пространством циклов графа G. При этом для любых двух цик-
лов C
i
и C
j
из множества C(G) таких, что C
i
∩ C
j
≠ ∅, существует некото-
рый третий цикл (C
i
⊕ C
j
) ∈ C(G), где символ ⊕ обозначает поразрядное
сложение по модулю два.
Базисом циклов графа G называется всякое множество простых цик-
лов B(G), порождающее пространство циклов этого графа. Любой цикл
пространства циклов графа G можно представить в виде линейной ком-
бинации базисных циклов. Если пространство циклов графа G имеет ба-
зис B(G), состоящий из n циклов B
1
, B
2
, ..., B
n
, то это пространство назы-
вается n-мерным пространством.
Деревом называется связный граф G, не содержащий ни одного цик-
ла. Остовный подграф графа G – это подграф, содержащий все вершины
графа G. Остовом D(G) графа G называется остовный подграф графа G,
являющийся деревом. Хордой остова связного графа G называется вся-
кое ребро графа G, не принадлежащее его остову.
a
b
c
d
e
k
1
2
4 5
6
а)
3
1
2
4 5
6
б)
3
a
b
c
d
e
g
f
l
f
g
k
l
m
1
2
4 5
6
в)
3
1
2
4 5
6
г)
3
a
b
c
d
e
a
b
c
d
e
f
g
k
l
m
f
g
k
l

Страницы