Изменения

'''0-цепьЦиклическое пространство графа''' (англ. ''cyclic graph space'' — линейная комбинация <math>\Sigma a_) {{i---}v_{i}</math> где <mathtex>a_{i} C = \in F_2, v_operatorname {iKer} \in V(I) </mathtex>, V — множество вершин графа.}}{{Определение|definition ='''1-цепь''' — линейная комбинация где <mathtex>I : B^m \Sigma a_{i}e_{i}rightarrow B^n </mathtex> где <math>a_{i} \in F_2, e_{i---} \in E</math>, Е — множество ребер графа.}}{{Определение|definition ='''Граничный линейный оператор , сопоставленный матрице инцидентности <mathtex>\deltaA </mathtex>''' — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то графа <mathtex>\delta e = u + vG </mathtex>. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи.

'''Циклический векторОбобщенный цикл графа <tex> G </tex>''' — 1-цепь с границей 0(англ.}}{{Определение|definition = ''generalized graph cycle'Циклическое пространство графа''' — пространство образованное множеством всех циклических векторов над полем ) {{---}} элемент линейного пространства <mathtex>F_2C </mathtex> = {0,1}.}}{{Теорема|statement =Циклическое пространство графа линейно.|proof =В циклическом пространстве графа задано сложение по модулю два.Нейтральным элементом относительно сложения является пустой граф.Любой элемент циклического пространства сам себе противоположен.Отсюда выполнение восьми условий линейности очевидно.

|id = lemma1|statement =Степени всех вершин всех Пространство <tex> C </tex> изоморфно <tex> T </tex>, где <tex> T </tex>{{---}} пространство, элементами которого являются наборы [[Основные_определения_теории_графов#def_graph_edge_1 | ребер]], из которых можно составить несколько простых реберно непересекающихся [[Основные_определения_теории_графов#def_graph_cycle_1 | циклов ]].|proof=Рассмотрим <tex> x \in C </tex>.  Рассмотрим граф <tex> G_1(V_1,E_1) </tex>, где <tex> E_1 </tex> {{---}} множество ребер, таких, что на соответствующих местах вектора <tex> x </tex> стоят единицы, а <tex> V_1 = V(G) </tex> . В силу определения обобщенного цикла: <tex> \forall v : v \in V_1 ~ deg(v) \equiv 0\mod~2 </tex>. Покажем по индукции, что <tex> G </tex> можно декомпозировать на несколько реберно непересекающихся простых циклов циклического пространства четны. Ведем индукцию по числу ребер.База индукции <tex> |E_1(G)|proof =0 </tex> очевидно выполняется. Рассмотрим циклический вектор <mathtex>G_1 </tex>. <tex> \sigmaforall v : v \in V_1 ~ deg(v) \equiv 0\mod~2 \Rightarrow |E_1(G)| > |V(G)| - 1 \Rightarrow </mathtex>существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф. Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.  Если степень какойрассмотреть набор реберно непересекающихся простых циклов некоторого графа <tex>G</tex> и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл, поставив <tex> 1 </tex> в соответствующие места <tex> x </tex>, во все остальные <tex> 0 </tex>.  {{Утверждение|statement = Если <tex>\textbf{C}</tex> {{---}} обобщенный цикл, соответствующий простому циклу <tex>C'</tex> графа <tex>G</tex>, то вершины нечетна <tex>I(\textbf{C}) = 0</tex>|proof=Пусть <tex>\textbf{C}</tex> {{---}} обобщенный цикл из условия, а <tex>C'</tex> {{---}} соответствующий ему простой цикл. Тогда <tex>I(\textbf{C}) = \bigoplus\limits_{e \in C'}c(e)</tex>, где <tex>c(e)</tex>{{---}} столбец в [[Матрица_инцидентности_графа | матрице инцидентности графа]] <tex>G</tex>, соответствующий ребру <tex>e</tex>. Так как каждая вершина в <tex>C'</tex> имеет степень <tex> 2 </tex>, то в для любого <tex>i \in \overline{0, |VG| - 1}</tex> верно <mathtex>|\{e \delta in C': c(e)_i = 1\sigma}| = 2</mathtex> она входит нечетное число раз, а значит <mathtex>I(\delta textbf{C})_i = 1 \sigmaoplus 1 = 0</tex>. Таким образом <tex>I(\textbf{C}) = 0</tex>. }} В силу линейности оператора <tex> I </tex> и того, что <tex>I( </mathtex> не равно простой цикл <tex> )=0</tex>, получаем что противоречит определению циклического вектора.<tex> Ix=0 </tex>

|statement =Размерность циклического пространства равна <tex> \operatorname {dim}(C) = m - n + k</tex>|proof=<tex> \operatorname {dim}(C)=\operatorname {dim}(\operatorname {Ker}(I))=m-\operatorname {Rang}(A) </tex>, где m <tex> \operatorname {Rang}(A) </tex> {{--- число }} максимальное количество ЛНЗ столбцов <tex> A </tex>. Если рассмотреть простой цикл <tex>C</tex> в <tex> G </tex>, то сумма столбцов соответствующих этим ребрам равна <tex>0</tex>, т. к. значение оператора <tex>I</tex> на соответствующем обобщенном цикле в точности равно сумме этих столбцов. Значит, эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер графа, n - число вершинсодержащих цикл, в соответствие сопоставить набор столбцов из <tex> A </tex>, то он будет ЛЗ {{Утверждение|statement=Если подмножество ребер из <tex>G</tex> не содержит цикл, k - число компонент связностито набор соответствующих столбцов из <tex>A</tex> ЛНЗ.|proof =Из теоремы о томПусть он ЛЗ, значит существует равная нулю линейная комбинация столбцов, где не все коэффициенты равны нулю. Возьмем столбцы, коэффициенты при которых не нулевые, тогда их линейная комбинация образует <tex>x \in C</tex>, что а значит соответствующие столбцам ребра разбиваются на простые циклы и исходное множество фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства ребер содержало цикл. Противоречие. }} Максимальное число ребер, которые мы можем выделить из G следует что размерность циклического пространства равна числу ребер и которые не входящих в каркас. Каркас содержит содержат цикл равно <tex> n - k ребер, значит размерность циклического пространства равна </tex> (в каждой компоненте связности выделим остовное дерево). Итого: <tex> \operatorname {dim}(C)=m - n + k.</tex>