Циклов графа

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

Если (s₁,..., s_k) и = (d₁,..., d_k) - некоторые двоичные наборы, то запись применяется для обозначения набора = (r₁,..., r_k), такого, что r _i = s _i + d _i для i = 1,..., k.

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

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

Будем представлять произвольные подграфы G_d = (V, U_d), где U_d U с помощью двоичных наборов ( ₁,..., _n), определяемых по следующему правилу: s _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 соответствует четный связный подграф.

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