Изменения
Нет описания правки
__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 = 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> существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф.
{{Утверждение|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>.}}
{{Теорема
|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=
Пусть он ЛЗ, значит существует равная нулю линейная комбинация столбцов, где не все коэффициенты равны нулю. Возьмем столбцы, коэффициенты при которых не нулевые, тогда их линейная комбинация образует <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>.
* Алгоритм: 1. Для вершины <tex>v_i</tex> найдём момент её последнего вхождения в путь {{---}} <tex>v_j</tex>. 2. Удалим отрезок пути от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно. Получившаяся последовательность вершин [[Ядро_и_образ_линейного_оператора|Ядро и рёбер графа останется путём от <tex>v_0</tex> до <tex>v_n</tex>, и в нём вершина <tex>v_i</tex> будет содержаться ровно один раз.Начнём процесс с вершины <tex>v_0</tex> и будем повторять его каждый раз для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.образ линейного оператора]]
=== Альтернативное =Примечания ==Выберем из всех путей между данными вершинами путь наименьшей длины.<references/>
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]