Цикловой ранг графа. Цикломатическое число

Если G(V, X) не является ациклическим графом, то в нем можно выделить цикл.

Независимыми называются циклы графа G, если они отличаются хотя бы одним ребром.

Множество всех независимых простых циклов, которые можно выделить в мультиграфе составляют цикловой базис графа.

Количество простых циклов в базисе называется цикломатическим числом или циклическим рангом графа G.

Обзначим цикломатическое число через (G).

Справедливо утверждение:

Если G(V, X) – связный граф, то (G) = m(G) – n(G) + p(G), где m(G) – количество ребер в графе, n(G) – количество вершин в графе, p(G) – количество компонент связности в графе.

Так, например, для дерева не существует цикловой базис, т.к. в дереве m = n – 1, р = 1(дерево – связный граф). Тогда цикломатическое число равно (G) = n – 1 – n +1 = 0. Следовательно в базисе нет ни одного цикла.

Рассмотрим алгоритм нахождения циклового базиса связного мультиграфа.

Если (G) = 0, то граф ациклический, циклового базиса не существует.

Пусть (G) > 0. Выделим в G любое остовное дерево Т. Пусть число вершин в графе G равно n, а число ребер – m. x₁, x₂,…, x_n-1 – ребра в Т (остовное дерево содержит все вершины графа, а по свойству дерева число ребер на 1 меньше числа вершин), x_n, x_n+1,…, x_m – остальные ребра графа G (заметим, что n  2, m  n). Число последних ребер m – (n – 1) = m – n + 1, и совпадает с цикломатическим числом связного графа. Добавляя любое из ребер x_i ( i = n, …, m) , к дереву Т, получаем некоторый подграф графа G, из которого выделяем простой цикл _i-(n-1) , проходящий через ребро x_i . Действуя таким образом, находим совокупность простых циклов {₁, _m-n+1}. Т.к. в каждом из циклов этой системы имеется ребро, не содержащееся в других циклах, то полученная система независимая, следовательно, является цикловым базисом графа G.

Используя данный алгоритм, определим цикловой базис мультиграфа, представленного на рисунке:

Вычислим цикломатическое число: n =4, m = 8, p =1, следовательно, (G) = 8 - 4 + 1 = 5. Значит, цикловой базис содержит 5 независимых циклов. Построим остовное дерево:

Добавим по одному удаленные из графа ребра и будем, таким образом, получать простые циклы:

Добавим ребро х₃, получим цикл v₁ x₂ x₃ x₅ v₁.

Добавим ребро x₆ , выделим простой цикл: v₁ x₂ x₃ x₆ v₁.

Добавим ребро x₇ , выделим простой цикл: v₁ x₂ x₇ x₁ v₁.

Добавим ребро x₈ , выделим простой цикл: v₁ x₂ x₈ x₁ v₁.

Добавим ребро x₄ , выделим простой цикл: v₁ x₂ x₃ x₄ х₁ v₁.

Получили пять циклов, составляющих цикловой базис графа.