Циклическое пространство графа — различия между версиями
| Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''0-цепь''' — линейная комбинация <math>\Sigma a_{i}v_{i}</math> где <math>a_{i} \in F_2, v_{i} \in V</math>, V — множество вершин графа. | + | '''0-цепь''' — линейная комбинация <math>\Sigma a_{i}v_{i}</math> где <math>a_{i} \in F_2, v_{i} \in V</math>, где <math> V</math> — множество вершин графа. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''1-цепь''' — линейная комбинация <math>\Sigma a_{i}e_{i}</math> где <math>a_{i} \in F_2, e_{i} \in E</math>, Е — множество ребер графа. | + | '''1-цепь''' — линейная комбинация <math>\Sigma a_{i}e_{i}</math> где <math>a_{i} \in F_2, e_{i} \in E</math>, где Е — множество ребер графа. |
}} | }} | ||
{{Определение | {{Определение | ||
Версия 19:16, 9 октября 2010
| Определение: |
| 0-цепь — линейная комбинация где , где — множество вершин графа. |
| Определение: |
| 1-цепь — линейная комбинация где , где Е — множество ребер графа. |
| Определение: |
| Граничный оператор — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то . Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи. |
| Определение: |
| Циклический вектор — 1-цепь с границей 0. |
| Определение: |
| Циклическое пространство графа — пространство образованное множеством всех циклических векторов над полем = {0,1}. |
| Теорема: |
Циклическое пространство графа линейно. |
| Доказательство: |
|
В циклическом пространстве графа задано сложение по модулю два. Нейтральным элементом относительно сложения является пустой граф. Любой элемент циклического пространства сам себе противоположен. Отсюда выполнение восьми условий линейности очевидно. |
| Лемма: |
Степени всех вершин всех циклов циклов циклического пространства четны. |
| Доказательство: |
| Рассмотрим циклический вектор . Если степень какой-то вершины нечетна то в она входит нечетное число раз, значит не равно 0, что противоречит определению циклического вектора. |
| Теорема: |
Размерность циклического пространства равна m - n + k, где m - число ребер графа, n - число вершин, k - число компонент связности. |
| Доказательство: |
| Из теоремы о том, что множество фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства G следует что размерность циклического пространства равна числу ребер не входящих в каркас. Каркас содержит n - k ребер, значит размерность циклического пространства равна m - n + k. |
