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

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

Пусть Т — остов связного графа G на вершинах и m ребрах. Ветви Т обозначим через а хорды — через . Пусть — базисный цикл и разрезающее множество по отношению к соответственно.

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

Чтобы доказать, что образуют базис подпространства циклов (разрезов) графа G, необходимо показать, что любой подграф подпространства циклов (разрезов) графа G можно представить в виде кольцевой суммы циклов (разрезов ). Рассмотрим любой подграф С подпространства циклов графа G. Пусть он содержит хорды Пусть

С — кольцевая сумма базисных циклов . Очевидно, что С содержит только хорды и не содержит других хорд остова Т. Поскольку подграф С также содержит только эти хорды, то не содержит ни одной хорды. Покажем, что пустое множество. Если это неверно, то по предыдущим рассуждениям множество содержит только ветви и, следовательно, не содержит цикла. С другой стороны, так как множество кольцевая сумма циклов, то по теореме 4.3 оно является либо циклом, либо объединением нескольких реберно-непересекающихся циклов. Получаем противоречие. Следовательно, пустое множество. Из этого следует, что Другими словами, каждый подграф подпространства циклов графа G можно представить в виде кольцевой суммы циклов Точно таким же образом мы можем доказать, что каждый подграф подпространства разрезов графа G можно представить в виде кольцевой суммы разрезов Итак, имеет место следующая теорема:

Теорема 4.6. Пусть G — связный граф на вершинах и ребрах. В" этом случае

1. Базисные циклы по отношению к остову графа G образуют базис подпространства циклов графа, и, следовательно, размерность подпространства циклов графа G равна т. е. цикломатическому числу графа

2. Базисные разрезающие множества по отношению к остову графа G образуют базис подпространства разрезов графа G, и, следовательно, размерность подпространства разрезов графа равна т. е. рангу графа

Рис. 4.3.

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

Таким образом, получаем следствие из предыдущей теоремы:

Следствие 4.6.1. Если граф на вершинах и ребрах имеет компонент, то 1. Размерность подпространства циклов графа G равна т. е. цикломагическому числу графа

2. Размерность подпространства разрезов графа G равна , т. е. рангу графа

В качестве примера рассмотрим граф G, изображенный на рис. 4.3. Ребра образуют остов графа G. Хордами остова Т являются . Базисные циклы по отношению к хордам и базисные рнчрезающие множества по отношению к вегвям определяются следующим образом:

Рассмотрим сначала подграф С, состоящий из ребер Нетрудно убедиться в том, что в подграфе С каждая вершина имеет четную степень и, следовательно, подграф С принадлежит подпространству циклов графа G.

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

Теперь рассмотрим разрез состоящий из ребер Снова, поскольку S содержит ветви , он должен равняться кольцевой сумме разрезающих множеств и . Это нетрудно проверить:

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