Изменения

__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>.

'''Циклическое пространство графа''' — (англ. ''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> ЛНЗ.

=== Доказательство построением =Применение ==Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Карпов В.Д. Теория графов - с.281 - Применения циклического пространства графа]</ref>.

Возьмём любой из существующих путей между нужными нам вершинами: <tex>v_0e_1v_1e_2v_2 ... e_nv_n</tex>== См.также ==*[[Линейный_оператор|Линейный оператор]]

* Алгоритм: 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/>

Предположение:== Источники информации == Пусть он не простой*Харари Ф.Тогда в нём содержатся две одинаковые вершины <tex>v_i = v_j<Теория графов /tex>, <tex>i < j</tex>пер. с англ. — изд. 4-е — М. Удалим из исходного пути отрезок от <tex>e_{i+1}</tex> до <tex>v_j</tex>: Книжный дом «ЛИБРОКОМ», включительно2009. Конечная последовательность также будет путём от <tex>v_0</tex> до <tex>v_n</tex> и станет короче исходной— с. Получено противоречие с условием: взятый нами путь оказался не кратчайшим54. Значит, предположение неверно, выбранный путь {{— ISBN 978-5-397-00622-}} простой.}}4

== Литература ==Харари Ф*Карпов В.Д. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.281