Изменения

Перейти к: навигация, поиск

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

4175 байт добавлено, 22:08, 20 октября 2016
Нет описания правки
__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>
}}
Определим пространство <tex> T </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> существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что каждому обобщенному циклу соответствуют ребрачетность степеней вершин не изменилась, которые образуют набор реберно непересекающихся простых цикловпо предположению индукции декомпозируем оставшийся граф.
Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.  Если рассмотреть набор реберно непересекающихся простых циклов некоторого графа <tex>G</tex> и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл (, поставив <tex> 1 </tex> в соответствующие места поставить <tex> 1 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>I( </tex> простой цикл <tex> )=0 </tex>, получаем что <tex> Ix=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> dim(C)=dim(Ker(i))=m-Rang(A) </tex>Пусть он ЛЗ, где <tex> Rang(A) = </tex> максимальное количество ЛНЗ значит существует равная нулю линейная комбинация столбцов <tex> A </tex>. Если рассмотреть цикл в <tex> G </tex>, то набор столбцов соответствующий ребрам в этом цикле ЛЗгде не все коэффициенты равны нулю. Отсюда следует, что если любому множеству реберВозьмем столбцы, содержащих цикл, в соответствие сопоставить набор столбцов из <tex> A </tex> то он будет ЛЗ. Если же множество ребер коэффициенты при которых не содержит цикл, то набор ЛНЗ (если бы он был ЛЗнулевые, тогда бы существовал их линейная комбинация образует <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
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
Анонимный участник

Навигация