Циклическое пространство графа

Определение:

0-цепь — линейная комбинация [math]\Sigma a_{i}v_{i}[/math] где [math]a_{i} \in F_2, v_{i} \in V[/math], V — множество вершин графа.

Определение:

1-цепь — линейная комбинация [math]\Sigma a_{i}e_{i}[/math] где [math]a_{i} \in F_2, e_{i} \in E[/math], Е — множество ребер графа.

Определение:

Граничный оператор [math]\delta[/math] — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то [math]\delta e = u + v[/math]. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи.

Определение:

Циклический вектор — 1-цепь с границей 0.

Определение:

Циклическое пространство графа — пространство образованное множеством всех циклических векторов над полем [math]F_2[/math] = {0,1}.

Теорема:

Циклическое пространство графа линейно.

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

Степени всех вершин всех циклов циклов циклического пространства четны.

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

[math]\triangleright[/math]

Рассмотрим циклический вектор [math]\sigma[/math]. Если степень какой-то вершины нечетна то в [math]\delta \sigma[/math] она входит нечетное число раз, значит [math]\delta \sigma[/math] не равно 0, что противоречит определению циклического вектора.

[math]\triangleleft[/math]

Теорема:

Размерность циклического пространства равна m - n + k, где m - число ребер графа, n - число вершин, k - число компонент связности.

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

[math]\triangleright[/math]

Из теоремы о том, что множество фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства G следует что размерность циклического пространства равна числу ребер не входящих в каркас. Каркас содержит n - k ребер, значит размерность циклического пространства равна m - n + k.

[math]\triangleleft[/math]