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