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

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

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

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

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

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

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

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

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

б) dv = åeixi, где ei = 1, если только ребро xi инцидентно v. На рис. 1-цепь s1=x1+x2+x4+x5 имеет «границу»

Ds1=(v1+v2)+(v1+v3)+(v2+v4)+(v5+v5) =

= v3+v4+v5+v6,

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

ds0=(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, если его можно представить в виде åejZj. Таким образом, можно сказать, что базис циклов графа 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) и следствие (б) дает уравнение Эйлера — Пуанкаре для графов.