Изменения
Нет описания правки
__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>.
{{Определение
|definition =
'''Циклическое пространство графа''' — (англ. ''cyclic graph space'') {{---}} <tex> C = \operatorname {Ker}(I) </tex>, где <tex> I : B^m \rightarrow B^n </tex> {{--- }} линейный оператор соопоставленый , сопоставленный матрице инциндентности инцидентности <tex> A </tex> графа <tex> G </tex>.
}}
{{Определение
|definition =
'''Обобщенный цикл графа <tex> G</tex>''' (англ. ''generalized graph cycle'') {{--- }} элемент линейного пространства <tex> C </tex>
}}
{{Лемма
|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> 1 </tex> в соответствующие места поставить <tex> 1 x </tex>, во все остальные <tex> 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>, где <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=
}}
== Литература(формулировки другие) Применение ==Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Карпов В.Д. Теория графов - с.281 - Применения циклического пространства графа]</ref>. == См. также ==*[[Линейный_оператор|Линейный оператор]] *[[Ядро_и_образ_линейного_оператора|Ядро и образ линейного оператора]] == Примечания ==<references/> == Источники информации ==*Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4 *Карпов В.Д. Теория графов - с.281
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]