Квазициклы. Пространство циклов графа

Циклом будем называть граф, у которого одна компонента связности является простым циклом, а остальные – изолированными вершинами.

В пространстве остовных подграфов графа выделим подпространство, содержащее все циклы графа .

Определение. Остовный подграф, у которого степени всех вершин четны, называется квазициклом.

Отметим, что всякий цикл является квазициклом, в том числе и пустой граф.

Покажем, что множество квазициклов замкнуто относительно операции сложения.

Лемма. Сумма двух квазициклов есть квазицикл.

Доказательство. Пусть и – квазициклы. Рассмотрим произвольную вершину , и пусть ее степени в и равны соответственно и . Тогда степень вершины в графе будет равна , где – число вершин, с которыми смежна в обоих графах и . Отсюда видно, что четно, если четны и .

Из леммы следует, что множество квазициклов является линейным векторным пространством над полем {0, 1}, которое называется пространством циклов графа . Обозначим это пространство через . Очевидно, что является подпространством векторного пространства остовных подграфов.