Независимые циклы и коциклы

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

F2={0, 1}, в котором 1 + 1=0 (хотя последующую теорию можно приспособить для произвольного поля). Так, число i, которое часто встречается в приводимых ниже определениях, равно 0 или 1.

Пусть, как обычно, G — граф с вершинами v1,..., vp и ребрами x1,..., xq.

0-цепь графаG формально определяется как линейная комбинацияivi вершин, а1-цепь- как линейная комбинацияivi ребер.Граничный операторотносит 1-цепям 0-цепи в соответствии со следующими правилами:

а) - линейный оператор;

б) если x = uv, то x = u + v.

С другой стороны, кограничный оператор относит 0-цепям 1-цепи в соответствии с правилами

а) - линейный оператор;

б) v =ixi, гдеi = 1, если только ребро xi инцидентноv. На рис. 1-цепь1=x1+x2+x4+x5 имеет «границу»

1=(v1+v2)+(v1+v3)+(v2+v4)+(v5+v5) =

= v3+v4+v5+v6,

а 0-цепь 0=v3+v4+v5+v6 имеет «кограницу»

0=(x2+x3+x6+x7)+(x4+x8) +

+ (x5+x6+x8+x9) + (x7+x9) =

= x2+x3+x4+x5

1-цепь с границей 0 называется циклическим векторомграфа G. Циклический вектор можно рассматривать как множество простых циклов, не имеющих попарно общих ребер. Множество всех циклических векторов образует над F2 векторное пространство, называемоепространством циклов графаG.Базис цикловграфа G определяется как базис пространства циклов графа G, состоящий только из простых циклов. Будем говорить, что циклический вектор Z зависит от простых циклов Z1, Z2,..., Zk, если его можно представить в видеjZj. Таким образом, можно сказать, что базис циклов графа G является максимальным набором независимых простых циклов графа G или минимальным набором простых циклов, от которых зависят все циклы.

Разрез связного графа - это множество ребер, удаление которых приводит к несвязному графу.Коцикломназывается минимальный разрез.Кограницейграфа G называется кограница некоторой его 0-цепи. Кограница набора U вершин есть не что иное, как множество всех ребер, соединяющих вершины из U с вершинами, не принадлежащими U. Очевидно, что каждая кограница является разрезом. Поскольку коцикл определяется как минимальный разрез графа G, а любой минимальный разрез есть кограница, то всякий коцикл является минимальной ненулевой кограницей. Множество всех кограниц графа G называетсяпространством коцикловграфа G, а базис этого пространства, состоящий только из коциклов, называетсябазисом коцикловграфа G.

Перейдем теперь к построению для пространства циклов графа G базиса, который соответствует остову Т. В связном графе G хордойостова Т называется ребро графа, не принадлежащее Т. Ясно, что подграф графа G, содержащий остов Т и его произвольную хорду, имеет только один (простой) цикл. Множество Z(T) всех таких циклов (каждая хорда «порождает» один цикл) независимо, так как каждый из них содержит ребро, не принадлежащее ни одному из остальных циклов. Более того, любой цикл Z зависит от множества Z(T), причем Z есть симметрическая разность циклов, которые определяются хордами остова Т, принадлежащими Z. Поэтому, определяяциклический ранг m(G) как число простых циклов базиса пространства циклов графа G, можно сформулировать следующий результат.

Теорема.Циклический ранг связного графа G равен числу хорд любого остова в G.

Следствие(а).Если G - связный (р, q)-граф, то m(G) = =q - p + l.

Следствие(б).Если G — это (р, q)-граф с k компонентами, то m(G)=q - p + k.

Подобные утверждения справедливы также для пространства коциклов. КодеревоТ* остова Т в связном графе G — это остовный подграф в G, содержащий только те ребра графа G, которые не принадлежат Т. Под кодеревом графа G понимается кодерево некоторого остова Т. На рис. показаны остов Т и его кодерево Т* для графа G, представленного также на рисунке Ребра графа G, не

принадлежащие Т*, назовем ветвямиграфа G . Подграф графа G, состоящий из Т* и любой одной ветви, содержит ровно один коцикл. Множество всех таких коциклов (каждая ветвь «порождает» один коцикл) является базисом пространства коциклов графа G.

На рисунке для графа G и его кодерева Т* изображены коциклы, образующие пространство коциклов,— они отмечены жирными линиями. Коциклический ранг m* (G) равен числу коциклов в базисе пространства коциклов графа G.

Теорема.Коциклический ранг связного графа G равен числу ребер любого его остова.

Как и в случае циклов, немедленно получаем два следствия.

Следствие(а).Если G — связный (р, а) - граф, то m* (G) = р-1.

Следствие (б).Если G — это (р, q)-граф с k компонентами, то m*(G)=p-k.

Замечание. Из теоремы можно получить частное утверждение (для одномерного случая) одного важного общего результата о симплициальных комплексах. Для каждого симплициального комплекса имеет место уравнение Эйлера- Пуанкаре

а0-a1+a2-... = b0-b1+b2-....,

где bn— числа Бетти, а аn— количества симплексов соответствующих размерностей. По определению bn, является рангом векторного пространства n-мерных циклов. Напомним , что любой граф есть симплициальный комплекс, вершины соответствуют 0-симплексам, а ребра соответствуют 1-симплексам. Для графа G имеем b = k (число его компонент связности) и b1=m(G) (число его независимых циклов). Поскольку графы не содержат n-симплексов приn> 1, то

an=bn=0 для всех n> 1. Поэтому а0—а1=b0-b1, так что р - q =k - m(G) и следствие (б) дает уравнение Эйлера — Пуанкаре для графов.