Циклическое пространство графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{{В разработке}}
 +
 +
Существует несколько определений циклического пространства графа.
 +
 +
== Определение 1 ==
 +
{{Определение
 +
|definition =
 +
'''Циклическое пространство графа''' —  множество множеств реберно непересекающихся циклов.
 +
}}
 +
== Определение 2 ==
 +
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Строка 19: Строка 30:
 
'''Циклическое пространство графа''' — пространство образованное множеством всех циклических векторов над полем <math>F_2</math> = {0,1}.
 
'''Циклическое пространство графа''' — пространство образованное множеством всех циклических векторов над полем <math>F_2</math> = {0,1}.
 
}}
 
}}
 +
== Эквивалентность определений ==
 +
{{Теорема
 +
|statement =
 +
Определения 1 и 2 эквивалентны.
 +
|proof =
 +
 +
}}
 +
== Свойства ==
 
{{Теорема
 
{{Теорема
 
|statement =
 
|statement =

Версия 23:14, 9 октября 2010

Эта статья находится в разработке!

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

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

Определение:
Циклическое пространство графа — множество множеств реберно непересекающихся циклов.

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


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


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

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

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

Свойства

Теорема:
Циклическое пространство графа линейно.
Доказательство:
[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]