Изменения

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

<tex> B^t </tex> {{---}} линейное пространство, элементами которого являются <tex> 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>

<tex> \operatorname {dim}(C)=\operatorname {dim}(\operatorname {Ker}(iI))=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> ЛНЗ (если бы . |proof=Пусть он был ЛЗ, значит существует равная нулю линейная комбинация столбцов, где не все коэффициенты равны нулю. Возьмем столбцы, коэффициенты при которых не нулевые, тогда бы существовал их линейная комбинация образует <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