5.8.2. Фундаментальное множество

ЦИКЛОВ ГРАФА

Определим операцию сложения двоичных наборов равной длины.

Если (₁, ... , _k) и = (₁, ... , _k)  некоторые двоичные наборы, то запись применяется для обозначения набора = (₁, ... , _k), такого, что _i = _i + _i для i = 1, . . . , k.

Пусть G = (V, U)  это неориентированный и не содержащий петель граф и U = (u₁, . . . , u_k).

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

Будем представлять произвольные подграфы G_d = (V, U_d), где U_d U с помощью двоичных наборов ( ₁, . . . , _n), определяемых по следующему правилу: _i = 1  u_i U_d.

Легко проверить, что всякий двоичный набор длины k представляет некоторый подграф графа G с таким же множеством вершин, что и у графа G.

Операция сложения двоичных наборов длины k порождает операцию сложения подграфов графа G, содержащих все вершины этого графа.

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

Будем обозначать сумму подграфов G₁ и G₂ графа G как G₁ + G₂.

Упражнение. Показать, что операция сложения подграфов некоторого графа является ассоциативной, т.е. для любых подграфов G₁, G₂ и G₃ графа G справедливо равенство

G₁ + (G₂ + G₃) = (G₁ + G₂) + G₃.

Ограничим множество рассматриваемых в дальнейшем подграфов произвольного заданного графа G только четными подграфами.

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

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

ТЕОРЕМА 5.7

Сумма четных подграфов произвольного графа G является четным подграфом G.

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

Пусть вершина v в подграфах G₁ и G₂ имеет степени 2s и 2t соответственно. Тогда в сумме G₁ + G₂ степень этой вершины равна 2s + 2t  2r , где r  число общих ребер графов G₁ и G₂, выходящих из вершины v.

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

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

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

+ =

С₁ С₂ С₁ + С₂

Рис. 5.23

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

Определение

Семейство F  простых циклов графа G называется фундаментальным множеством циклов этого графа, если для него выполнены следующие свойства:

1) любой цикл семейства F не может быть выражен в виде суммы других циклов из F;

2. всякий простой цикл в G представляется в виде суммы некоторых циклов из F.

Пусть G = (V, U)  некоторый граф. Построим специальное семейство циклов в этом графе с помощью процедуры, основанной на последовательном размыкании циклов в графе.

1. Если в G имеются циклические ребра, то возьмем в этом графе любой элементарный цикл ненулевой длины и обозначим его как С₁.

2. Удалим из G некоторое ребро u₁ этого цикла.

3. Пусть уже определены циклы С₁, . . . , С_k и из графа G последовательно удалены ребра u₁, . . . , u_k.

Если полученный в результате граф G^* имеет хотя бы одно циклическое ребро, то возьмем в этом графе любой элементарный цикл С_k+1, содержащий некоторое циклическое ребро u_k+1, и удалим из графа G^* это ребро.

4. Действие 3 повторяется до тех пор, пока в получаемых на каждом шаге графах содержатся циклические ребра.

Сформулированная процедура заканчивается за конечное число повторений шага 3. Ее результатом является конечное множество простых циклов С₁, . . . , С_k. Обозначим это семейство как F.