Размерность и базис пространства циклов

Компактное представление пространства дает его базис. Если выписать все простые циклы графа , то в большинстве случаев они не образуют базис, так как некоторые из этих циклов могут быть суммами других. Построить базис пространства , состоящий из простых циклов, можно следующим образом. Выберем в графе какой-нибудь остов (каркас) . Пусть – все хорды графа . Если добавить к хорду , то в графе образуется единственный цикл . Таким образом, получим семейство из циклов, которые называются фундаментальными (базисными) циклами относительно остова .

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

Доказательство.

Зафиксируем некоторый остов и рассмотрим фундаментальные циклы относительно этого остова. В каждом из этих циклов имеется хорда , принадлежащая циклу и не принадлежащая никакому из остальных. Поэтому при сложении этого цикла с другими фундаментальными циклами эта хорда будет присутствовать в суммарном графе. Следовательно, сумма различных фундаментальных циклов никогда не будет пустым графом, то есть фундаментальные циклы линейно независимы.

Покажем теперь, что любой квазицикл графа является суммой фундаментальных циклов. Пусть – все ребра , не принадлежащие (хорды графа ). Рассмотрим квазицикл . Каждое из ребер () входит ровно в два слагаемых этой суммы – в и в . Следовательно, при сложении эти ребра уничтожатся. Все остальные ребра, присутствующих в графах-слагаемых, принадлежат . Значит, – подграф графа . Поскольку в нет циклов, то . Отсюда .

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

Пример. Построим систему базисных циклов для графа, представленного на рис. 2.

° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

Рис. 2. Граф и его остовные деревья , и

Выделим остовное дерево . Присоединяя к дереву по очереди хорды , , и , получим 4 базисных цикла (рис. 3).

° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

Рис. 3. Базисные циклы графа

Для дерева получим другую систему базисных циклов (рис. 4).

° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

Циклы одной из систем можно выразить как линейные комбинации циклов из другой системы. В данном случае имеем:

Обратное преобразование имеет вид: