Циклическое пространство графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Существует несколько определений циклического пространства графа.
+
== Определение ==
 +
Пусть <tex> m </tex> - количество ребер графа <tex> G </tex>.
  
== Определение 1 ==
+
Пусть <tex> n </tex> - количество вершин графа <tex> G </tex>.
{{Определение
+
 
|definition =
+
<tex> B^k </tex> {{---}} линейное пространство элементами которого являются <tex> k </tex>{{---}}мерные двоичные вектора и их сложение определено как сложение по модулю <tex> 2 </tex>.  
'''Циклическое пространство графа''' —  семейство множеств реберно непересекающихся циклов. <tex> C = \{ P | P \subset C_0, \forall a, b \in P \ a \ne b : a \cap b = \varnothing \} </tex>, где <tex>C_0</tex> — множество всех циклов графа.
 
}}
 
  
== Определение 2 ==
+
Рассмотрим матрицу инцидентности <tex> G </tex>.
  
 +
Сопоставим ей линейный оператор <tex> I : R^m \rightarrow R^n </tex>
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''0-цепь''' — линейная комбинация <tex>\Sigma a_{i}v_{i}</tex> где <tex>a_{i} \in F_2, v_{i} \in V</tex>, где <tex> V</tex> — множество вершин графа.
+
'''Циклическое пространство графа''' — <tex> C = Ker(I) </tex>
}}
 
{{Определение
 
|definition =
 
'''1-цепь''' — линейная комбинация <tex>\Sigma a_{i}e_{i}</tex> где <tex>a_{i} \in F_2, e_{i} \in E</tex>, где <tex>E</tex> — множество ребер графа.
 
}}
 
{{Определение
 
|definition =
 
'''Граничный оператор <tex>\delta</tex>''' — линейный оператор, сопоставляющий 1-цепи 0-цепь таким образом, что если <tex>e = (u, v)</tex>, то <tex>\delta e = u + v</tex>. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи. Таким образом, границей 1-цепи является сумма вершин инцидентных нечетному числу ребер из 1-цепи.
 
}}
 
{{Определение
 
|definition =
 
'''Циклический вектор''' — 1-цепь с границей 0.
 
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Циклическое пространство графа''' — пространство, образованное множеством всех циклических векторов над полем <tex>F_2 = \{0, 1\}</tex>.
+
'''Обобщенный цикл графа G''' - элемент линейного пространства <tex> C </tex>
}}
 
 
 
== Эквивалентность определений ==
 
{{Теорема
 
|statement =
 
Определения 1 и 2 эквивалентны.
 
|proof =
 
<tex>1 \Rightarrow 2</tex>
 
Рассмотрим множество <tex> Z </tex> реберно непересекающихся циклов. 1-цепь <tex>\sigma</tex>, состоящая из всех ребер из <tex>Z</tex>, имеет границу 0, так как для любого ребра <tex>e_{i} = (u_{i}, v_{i})\in Z \ u_{i}, v_{i}</tex> встречаются в <tex>\delta\sigma </tex> четное число раз.
 
 
 
<tex>2 \Rightarrow 1</tex> Рассмотрим 1-цепь <tex>\sigma</tex>. Из того, что граница <tex>\sigma</tex> равна 0 следует, что для любого <tex>e = (u, v) \in \sigma </tex> <tex>u</tex> и <tex>v</tex> встречаются в <tex>\delta \sigma </tex> четное число раз. Значит, <tex>\sigma</tex> можно разбить на дизъюнктные подмножества <tex>E_1,..., E_{i},</tex> такие что путь, состоящий из <tex>u_1, e_1, v_1,...,u_{k}, e_{k}, v_{k}</tex>, где <tex>e_{k} =(u_{k}, v_{k})  \in E_{i}</tex>, является циклом. Так как каждое ребро графа встречается не более одного раза, то эти циклы будут реберно непересекающимися.
 
}}
 
 
 
== Свойства ==
 
{{Теорема
 
|statement =
 
Циклическое пространство графа линейно.
 
|proof =
 
В циклическом пространстве графа задано сложение по модулю два.
 
Нейтральным элементом относительно сложения является пустой граф.
 
Любой элемент циклического пространства сам себе противоположен.
 
Отсюда выполнение восьми условий линейности очевидно.
 
 
}}
 
}}
{{Лемма
 
|statement =
 
Степени всех вершин всех циклов циклического пространства четны.
 
|proof =
 
Рассмотрим циклический вектор <tex>\sigma</tex>. Если степень какой-то вершины нечетна, то в <tex>\delta \sigma</tex> она входит нечетное число раз, значит <tex>\delta \sigma</tex> не равно 0, что противоречит определению циклического вектора.
 
}}
 
{{Теорема
 
|statement =
 
Размерность циклического пространства равна <tex>m - n + k</tex>, где <tex>m</tex> — число ребер графа, <tex>n</tex> — число вершин, <tex>k</tex> — число компонент связности.
 
|proof =
 
Из теоремы о том, что множество [[Фундаментальные циклы графа|фундаментальных циклов]] относительно любого каркаса <tex>T</tex> графа <tex>G</tex> образует базис циклического пространства <tex>G</tex> следует, что размерность циклического пространства равна числу ребер, не входящих в каркас. Каркас содержит <tex>n - k</tex> ребер, значит размерность циклического пространства равна <tex>m - n + k</tex>.
 
}}
 
 
 
== Литература ==
 
== Литература ==
 
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.
 
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4.

Версия 04:08, 2 ноября 2011

Определение

Пусть [math] m [/math] - количество ребер графа [math] G [/math].

Пусть [math] n [/math] - количество вершин графа [math] G [/math].

[math] B^k [/math] — линейное пространство элементами которого являются [math] k [/math]—мерные двоичные вектора и их сложение определено как сложение по модулю [math] 2 [/math].

Рассмотрим матрицу инцидентности [math] G [/math].

Сопоставим ей линейный оператор [math] I : R^m \rightarrow R^n [/math]

Определение:
Циклическое пространство графа[math] C = Ker(I) [/math]


Определение:
Обобщенный цикл графа G - элемент линейного пространства [math] C [/math]

Литература

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