Изменения

Существует несколько определений циклического пространства __TOC__== Циклическое пространство графа==Пусть <tex> m = |E(G)| </tex>, <tex> n = |V(G)| </tex>, <tex> k </tex> {{---}} количество компонент связности <tex> G </tex>. <tex> B^t </tex> {{---}} линейное пространство, элементами которого являются <tex> t </tex>-мерные двоичные вектора и их сложение определено, как сложение по модулю <tex> 2 </tex>.

'''Циклическое пространство графа''' — семейство множеств реберно непересекающихся циклов(англ. ''cyclic graph space'') {{---}} <tex> C = \operatorname { P | P \subset C_0Ker}(I) </tex>, \forall a, b \in P \ a \ne b где <tex> I : a B^m \cap b = \varnothing \} rightarrow B^n </tex>{{---}} линейный оператор, где сопоставленный матрице инцидентности <tex>C_0A </tex> — множество всех циклов графа<tex> G </tex>.

'''0-цепь''' — линейная комбинация Обобщенный цикл графа <tex>\Sigma a_{i}v_{i}G </tex> где <tex>a_''' (англ. ''generalized graph cycle'') {{i---} \in F_2, v_{i} \in Vэлемент линейного пространства </tex>, где <tex> VC </tex> — множество вершин графа.

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

== Эквивалентность определений Размерность линейного пространства обобщенных циклов ==

|statement = Определения 1 и 2 эквивалентны.<tex> \operatorname {dim}(C) = m - n + k </tex>|proof = <tex>1 \Rightarrow 2operatorname {dim}(C)=\operatorname {dim}(\operatorname {Ker}(I))=m-\operatorname {Rang}(A) </tex>, где <tex> \operatorname {Rang}(A) </tex>Рассмотрим множество {{---}} максимальное количество ЛНЗ столбцов <tex> Z A </tex> реберно непересекающихся циклов. 1-цепь Если рассмотреть простой цикл <tex>\sigmaC</tex> состоящая из всех ребер из в <tex>ZG </tex> имеет границу , то сумма столбцов соответствующих этим ребрам равна <tex>0</tex>, т. к. значение оператора <tex>I</tex> на соответствующем обобщенном цикле в точности равно сумме этих столбцов. Значит, так как для любого ребра эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из <tex> A </tex>e_{i} = (u_{i}, v_то он будет ЛЗ {i})\in Z \ u_{i}Утверждение|statement=Если подмножество ребер из <tex>G</tex> не содержит цикл, v_{i}то набор соответствующих столбцов из <tex>A</tex> встречаются в ЛНЗ. |proof=Пусть он ЛЗ, значит существует равная нулю линейная комбинация столбцов, где не все коэффициенты равны нулю. Возьмем столбцы, коэффициенты при которых не нулевые, тогда их линейная комбинация образует <tex>x \delta\sigma in C</tex> четное число раз, а значит соответствующие столбцам ребра разбиваются на простые циклы и исходное множество ребер содержало цикл. Противоречие.}}

Максимальное число ребер, которые мы можем выделить из G и которые не содержат цикл равно <tex>2 \Rightarrow 1</tex> Рассмотрим 1n -цепь <tex>\sigma</tex>. Из того, что граница <tex>\sigmak </tex> равна 0 следует, что для любого <tex>e = (u, vв каждой компоненте связности выделим остовное дерево) \in \sigma . Итого: </tex> <tex>u</tex> и <tex>v</tex> встречаются в <tex>\delta \sigma </tex> четное число раз. Значит <math>\sigma</math> можно разбить на дизъюнктные подмножества <tex>E_1,..., E_operatorname {i},</tex> такие, что путь состоящий из <tex>u_1, e_1, v_1,...,u_{k}, e_{k}, v_{k}</tex>, где <tex>e_{kdim} (C)=(u_{k}, v_{m - n + k}) \in E_{i}</tex> является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися.

== Свойства Применение =={{Теорема|statement =Циклическое пространство графа линейнопозволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа.|proof =В циклическом пространстве частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа задано сложение по модулю два<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Карпов В.Нейтральным элементом относительно сложения является пустой графД. Теория графов - с.Любой элемент 281 - Применения циклического пространства сам себе противоположенграфа]</ref>.Отсюда выполнение восьми условий линейности очевидно== См.также ==}}*[[Линейный_оператор|Линейный оператор]]{{Лемма*[[Ядро_и_образ_линейного_оператора|statement =Ядро и образ линейного оператора]]Степени всех вершин всех циклов циклического пространства четны.|proof == Примечания ==Рассмотрим циклический вектор <tex>\sigma<references/tex>. Если степень какой-то вершины нечетна, то в <tex>\delta \sigma</tex> она входит нечетное число раз, значит <tex>\delta \sigma</tex> не равно 0, что противоречит определению циклического вектора.}}{{Теорема|statement == Источники информации ==Размерность циклического пространства равна <tex>m *Харари Ф. Теория графов / пер. с англ. — изд. 4- n + k</tex>е — М.: Книжный дом «ЛИБРОКОМ», где <tex>m</tex> 2009. — с.54. — ISBN 978-5- число ребер графа, <tex>n</tex> 397- число вершин, <tex>k</tex> 00622- число компонент связности.4|proof =Из теоремы о том, что множество [[Фундаментальные циклы графа|фундаментальных циклов]] относительно любого каркаса <tex>T</tex> графа <tex>G</tex> образует базис циклического пространства <tex>G</tex> следует что размерность циклического пространства равна числу ребер не входящих в каркас*Карпов В.Д. Каркас содержит <tex>n - k</tex> ребер, значит размерность циклического пространства равна <tex>m Теория графов - n + k</tex>с.}}281

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