Определение: Циклический ранг CR(G) или цикломатическое число графа G есть размерность подпространства четных подграфов линейного пространства всех подграфов графа G.

Справедливы следующие утверждения:
1) для связного (p,q) графа G
a) CR(G) = dim (L_чет) = q — p+1
b) CR(G) = рангу матрицы простых циклов в G.
c) CR(G) = числу хорд в G.
d) СR(G) = максимальному числу линейно независимых простых циклов в G.

2) CR(G) = dim (L_чет) ≥ 0

3) Для связного (p,q) графа G следующие утверждения эквивалентны
a) Граф G есть дерево
b) q — p+1 = 0
c) dim (L_чет) = 0
d) CR(G) = 0
e) Граф G не имеет циклов.
f) Число хорд в графе G равно 0.

4) Для связного (p,q) графа G следующие утверждения эквивалентны.
a) Граф G имеет единственный простой цикл
b) q-p+1=1
c) dim (L_чет) =1
d) CR(G) =1
e) Ранг матрицы простых циклов в G равен 1.
f) Число хорд в G равно 1.

5) Если связный (p,q) — граф G имеет к компонент связности G_i, i=1,2,..k Причем каждое G_i есть (p_i,q_i) граф, то CR(G) = dim (L_чет в G) = ∑_i=1…к dim (L_чет в G_i) = q-p+k

6) Фундаментальная система циклов (базис пространства L_чет линейного пространства четного подграфа графа G) можно построить, взяв с каждой хордой графа G один из простых циклов, проходящих через эту хорду. Фундаментальная система циклов можно построить также, последовательно выделяя в G очередной простой цикл и потом удалая из G произвольное ребро (хорду) этого цикла. В оставшемся графе опять выбирать цикл и т.д., пока циклы последовательно получающихся графов не будут исчерпаны. В результате — Ф.С.Ц. графа G. Оставшийся граф образует каркас в G.

Комментарии запрещены.