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

Существует несколько определений циклического пространства графа.

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

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

Циклическое пространство графа — семейство множеств реберно непересекающихся циклов. [math] C = \{ P | P \subset C_0, \forall a, b \in P \ a \ne b : a \cap b = \varnothing \} [/math], где [math]C_0[/math] — множество всех циклов графа.

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

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

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

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

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

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

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

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

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

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

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

Эквивалентность определений

Теорема:

Определения 1 и 2 эквивалентны.

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

[math]\triangleright[/math]

[math]1 \rightarrow 2[/math] Рассмотрим множество [math] Z [/math] реберно непересекающихся циклов. 1-цепь [math]\sigma[/math] состоящая из всех ребер из [math]Z[/math]. имеет границу 0, так как для любого ребра [math]e_{i} = (u_{i}, v_{i})\in Z \ u_{i}, v_{i}[/math] встречаются в [math]\delta\sigma [/math] четное число раз. [math]2 \rightarrow 1[/math] Рассмотрим 1-цепь [math]\sigma[/math]. Из того, что граница [math]\sigma[/math] равна 0 следует, что для любого [math]e = (u, v) \in \sigma [/math] u и v встречаются в [math]\delta \sigma [/math] четное число раз. Значит [math]\sigma[/math] можно разбить на дизъюнктные подмножества [math]E_1,..., E_{i},[/math] такие, что путь состоящий из [math]u_1, e_1, v_1,...,u_{k}, e_{k}, v_{k}[/math], где [math]e_{k} =(u_{k}, v_{k}) \in E_{i}[/math] является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися.

[math]\triangleleft[/math]

Свойства

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Литература

Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.