Изменения

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

<tex> B^k t </tex> {{---}} линейное пространство, элементами которого являются <tex> k t </tex>{{---}}мерные двоичные вектора и их сложение определено, как сложение по модулю <tex> 2 </tex>.

'''Циклическое пространство графа''' — (англ. ''cyclic graph space'') {{---}} <tex> C = \operatorname {Ker}(I) </tex>, где <tex> I : B^m \rightarrow B^n </tex> {{---}} линейный оператор, сопоставленный матрице инцидентности <tex> A </tex> графа <tex> G </tex>.

'''Обобщенный цикл графа <tex> G</tex>''' (англ. ''generalized graph cycle'') {{--- }} элемент линейного пространства <tex> 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)|=0 </tex> очевидно выполняется. Рассмотрим <tex> G_1 </tex>. <tex> \forall v : v \in V_1 ~ deg(v) \equiv 0\mod~2 \Rightarrow |E_1(G)| > |V(G)| - 1 \Rightarrow </tex> существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф.

В силу определения обобщенного цикла: <tex> \forall v : v \in V_1 ~ deg(v) \equiv 0(mod~2) </tex>Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.

Значит, Если рассмотреть набор реберно непересекающихся простых циклов некоторого графа <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> верно <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> C I( </tex> изоморфно пространству простой цикл <tex> T )=0 </tex>, элементами которого являются множества ребер, из которых можно составить несколько реберно непересекающихся простых циклов.получаем что <tex> Ix=0 </tex>}}

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

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

== Литература(формулировки другие) Применение ==Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Карпов В.Д. Теория графов - с.281 - Применения циклического пространства графа]</ref>. == См. также ==*[[Линейный_оператор|Линейный оператор]] *[[Ядро_и_образ_линейного_оператора|Ядро и образ линейного оператора]] == Примечания ==<references/> == Источники информации ==*Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4 *Карпов В.Д. Теория графов - с.281