Изменения

Перейти к: навигация, поиск

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

42 байта убрано, 23:11, 13 октября 2010
Нет описания правки
{{Определение
|definition =
'''Циклическое пространство графа''' — множество множеств реберно непересекающихся циклов. <mathtex> C = \{ P | P \subset C_0, \forall a, b \in P \ a \ne b : a \cup b = \emptyset \} </mathtex>, где <math>C_0</math> — множество всех циклов графа.
}}
{{Определение
|definition =
'''0-цепь''' — линейная комбинация <mathtex>\Sigma a_{i}v_{i}</mathtex> где <mathtex>a_{i} \in F_2, v_{i} \in V</mathtex>, где <mathtex> V</mathtex> — множество вершин графа.
}}
{{Определение
|definition =
'''1-цепь''' — линейная комбинация <mathtex>\Sigma a_{i}e_{i}</mathtex> где <mathtex>a_{i} \in F_2, e_{i} \in E</mathtex>, где Е — множество ребер графа.
}}
{{Определение
|definition =
'''Граничный оператор <math>\delta</math>''' — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то <mathtex>\delta e = u + v</mathtex>. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи.
}}
{{Определение
{{Определение
|definition =
'''Циклическое пространство графа''' — пространство образованное множеством всех циклических векторов над полем <mathtex>F_2</mathtex> = {0,1}.
}}
== Эквивалентность определений ==
Определения 1 и 2 эквивалентны.
|proof =
* <mathtex>1 \rightarrow 2</mathtex>Рассмотрим множество <math>\Zeta</math> реберно непересекающихся циклов. 1-цепь <mathtex>\sigma</mathtex> состоящая из всех ребер из <math>\Zeta</math> имеет границу 0, так как для любого ребра <math>e_{i} = (u_{i}, v_{i})\in \Zeta \ u_{i}, v_{i}</math> встречаются в <mathtex>\delta\sigma </mathtex> четное число раз.* <mathtex>2 \rightarrow 1</mathtex>Рассмотрим 1-цепь <mathtex>\sigma</mathtex>. Из того, что граница <mathtex>\sigma</mathtex> равна 0 следует, что для любого <mathtex>e = (u, v) \in \sigma </mathtex> u и v встречаются в <mathtex>\delta \sigma </mathtex> четное число раз. Значит <math>\sigma</math> можно разбить на дизъюнктные подмножества <mathtex>E_1,..., E_{i},</mathtex> такие, что путь состоящий из <mathtex>u_1, e_1, v_1,...,u_{k}, e_{k}, v_{k}</mathtex>, где <mathtex>e_{k} =(u_{k}, v_{k}) \in E_{i}</mathtex> является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися.
}}
Степени всех вершин всех циклов циклического пространства четны.
|proof =
Рассмотрим циклический вектор <mathtex>\sigma</mathtex>. Если степень какой-то вершины нечетна то в <mathtex>\delta \sigma</mathtex> она входит нечетное число раз, значит <mathtex>\delta \sigma</mathtex> не равно 0, что противоречит определению циклического вектора.
}}
{{Теорема
Анонимный участник

Навигация