Изменения
Нет описания правки
__TOC__== Определение Циклическое пространство графа ==
Пусть <tex> m = |E(G)| </tex>, <tex> n = |V(G)| </tex>, <tex> k </tex> {{---}} количество компонент связности <tex> G </tex>.
<tex> B^k t </tex> {{---}} линейное пространство , элементами которого являются <tex> k 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 </tex> {{---}} <tex> = V(G) </tex> .
В силу определения обобщенного цикла : <tex> \forall v : v \in V_1 ~ deg(v) \equiv 0(\mod~2) </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>I( </tex> простой цикл <tex> )=0 </tex>, получаем что <tex> Ix=Теорема о существовании простого пути в случае существования пути0 </tex>}} == Размерность линейного пространства обобщенных циклов ==
{{Теорема
|statement=
|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== Доказательство построением ===Пусть он ЛЗ, значит существует равная нулю линейная комбинация столбцов, где не все коэффициенты равны нулю. Возьмем столбцы, коэффициенты при которых не нулевые, тогда их линейная комбинация образует <tex>x \in C</tex>, а значит соответствующие столбцам ребра разбиваются на простые циклы и исходное множество ребер содержало цикл. Противоречие. }}
=== Альтернативное =См. также ==Выберем из всех путей между данными вершинами путь наименьшей длины.*[[Линейный_оператор|Линейный оператор]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
