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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Циклическое пространство графа''' —  множество множеств реберно непересекающихся циклов. <math>  C = \{ P | P \subset C_0, \forall a, b \in P \ a \ne b : a \cup b = \emptyset \} </math>, где <math>C_0</math> — множество всех циклов графа.
+
'''Циклическое пространство графа''' —  множество множеств реберно непересекающихся циклов. <tex>  C = \{ P | P \subset C_0, \forall a, b \in P \ a \ne b : a \cup b = \emptyset \} </tex>, где <math>C_0</math> — множество всех циклов графа.
 
}}
 
}}
  
Строка 11: Строка 11:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''0-цепь''' — линейная комбинация <math>\Sigma a_{i}v_{i}</math> где <math>a_{i} \in F_2, v_{i} \in V</math>, где <math> V</math> — множество вершин графа.
+
'''0-цепь''' — линейная комбинация <tex>\Sigma a_{i}v_{i}</tex> где <tex>a_{i} \in F_2, v_{i} \in V</tex>, где <tex> V</tex> — множество вершин графа.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''1-цепь''' — линейная комбинация <math>\Sigma a_{i}e_{i}</math> где <math>a_{i} \in F_2, e_{i} \in E</math>, где Е — множество ребер графа.
+
'''1-цепь''' — линейная комбинация <tex>\Sigma a_{i}e_{i}</tex> где <tex>a_{i} \in F_2, e_{i} \in E</tex>, где Е — множество ребер графа.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Граничный оператор <math>\delta</math>''' — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то <math>\delta e = u + v</math>. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи.
+
'''Граничный оператор <math>\delta</math>''' — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то <tex>\delta e = u + v</tex>. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 27: Строка 27:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Циклическое пространство графа''' — пространство образованное множеством всех циклических векторов над полем <math>F_2</math> = {0,1}.
+
'''Циклическое пространство графа''' — пространство образованное множеством всех циклических векторов над полем <tex>F_2</tex> = {0,1}.
 
}}
 
}}
 
== Эквивалентность определений ==
 
== Эквивалентность определений ==
Строка 34: Строка 34:
 
Определения 1 и 2 эквивалентны.
 
Определения 1 и 2 эквивалентны.
 
|proof =  
 
|proof =  
* <math>1 \rightarrow 2</math>
+
* <tex>1 \rightarrow 2</tex>
Рассмотрим множество <math>\Zeta</math> реберно непересекающихся циклов. 1-цепь <math>\sigma</math> состоящая из всех ребер из <math>\Zeta</math>  
+
Рассмотрим множество <math> \Zeta </math> реберно непересекающихся циклов. 1-цепь <tex>\sigma</tex> состоящая из всех ребер из <math>\Zeta</math>  
имеет границу 0, так как для любого ребра <math>e_{i} = (u_{i}, v_{i})\in \Zeta \ u_{i}, v_{i}</math> встречаются в <math>\delta\sigma </math> четное число раз.
+
имеет границу 0, так как для любого ребра <math>e_{i} = (u_{i}, v_{i})\in \Zeta \ u_{i}, v_{i}</math> встречаются в <tex>\delta\sigma </tex> четное число раз.
* <math>2 \rightarrow 1</math>
+
* <tex>2 \rightarrow 1</tex>
Рассмотрим 1-цепь <math>\sigma</math>. Из того, что граница <math>\sigma</math> равна 0 следует, что для любого <math>e = (u, v) \in \sigma </math> u и v встречаются в <math>\delta \sigma </math> четное число раз. Значит <math>\sigma</math> можно разбить на дизъюнктные подмножества <math>E_1,..., E_{i},</math> такие, что путь состоящий из <math>u_1, e_1, v_1,...,u_{k}, e_{k}, v_{k}</math>, где <math>e_{k} =(u_{k}, v_{k})  \in E_{i}</math> является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися.
+
Рассмотрим 1-цепь <tex>\sigma</tex>. Из того, что граница <tex>\sigma</tex> равна 0 следует, что для любого <tex>e = (u, v) \in \sigma </tex> u и v встречаются в <tex>\delta \sigma </tex> четное число раз. Значит <math>\sigma</math> можно разбить на дизъюнктные подмножества <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> является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися.
 
}}
 
}}
  
Строка 55: Строка 55:
 
Степени всех вершин всех циклов циклического пространства четны.
 
Степени всех вершин всех циклов циклического пространства четны.
 
|proof =
 
|proof =
Рассмотрим циклический вектор <math>\sigma</math>. Если степень какой-то вершины нечетна то в <math>\delta \sigma</math> она входит нечетное число раз, значит <math>\delta \sigma</math> не равно 0, что противоречит определению циклического вектора.
+
Рассмотрим циклический вектор <tex>\sigma</tex>. Если степень какой-то вершины нечетна то в <tex>\delta \sigma</tex> она входит нечетное число раз, значит <tex>\delta \sigma</tex> не равно 0, что противоречит определению циклического вектора.
 
}}
 
}}
 
{{Теорема
 
{{Теорема

Версия 23:11, 13 октября 2010

Существует несколько определений циклического пространства графа.

Определение 1

Определение:
Циклическое пространство графа — множество множеств реберно непересекающихся циклов. [math] C = \{ P | P \subset C_0, \forall a, b \in P \ a \ne b : a \cup b = \emptyset \} [/math], где [math]C_0[/math] — множество всех циклов графа.


Определение 2

Определение:
0-цепь — линейная комбинация [math]\Sigma a_{i}v_{i}[/math] где [math]a_{i} \in F_2, v_{i} \in V[/math], где [math] V[/math] — множество вершин графа.


Определение:
1-цепь — линейная комбинация [math]\Sigma a_{i}e_{i}[/math] где [math]a_{i} \in F_2, e_{i} \in E[/math], где Е — множество ребер графа.


Определение:
Граничный оператор [math]\delta[/math] — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то [math]\delta e = u + v[/math]. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи.


Определение:
Циклический вектор — 1-цепь с границей 0.


Определение:
Циклическое пространство графа — пространство образованное множеством всех циклических векторов над полем [math]F_2[/math] = {0,1}.

Эквивалентность определений

Теорема:
Определения 1 и 2 эквивалентны.
Доказательство:
[math]\triangleright[/math]
  • [math]1 \rightarrow 2[/math]

Рассмотрим множество [math] \Zeta [/math] реберно непересекающихся циклов. 1-цепь [math]\sigma[/math] состоящая из всех ребер из [math]\Zeta[/math] имеет границу 0, так как для любого ребра [math]e_{i} = (u_{i}, v_{i})\in \Zeta \ u_{i}, v_{i}[/math] встречаются в [math]\delta\sigma [/math] четное число раз.

  • [math]2 \rightarrow 1[/math]
Рассмотрим 1-цепь [math]\sigma[/math]. Из того, что граница [math]\sigma[/math] равна 0 следует, что для любого [math]e = (u, v) \in \sigma [/math] u и v встречаются в [math]\delta \sigma [/math] четное число раз. Значит [math]\sigma[/math] можно разбить на дизъюнктные подмножества [math]E_1,..., E_{i},[/math] такие, что путь состоящий из [math]u_1, e_1, v_1,...,u_{k}, e_{k}, v_{k}[/math], где [math]e_{k} =(u_{k}, v_{k}) \in E_{i}[/math] является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися.
[math]\triangleleft[/math]

Свойства

Теорема:
Циклическое пространство графа линейно.
Доказательство:
[math]\triangleright[/math]

В циклическом пространстве графа задано сложение по модулю два. Нейтральным элементом относительно сложения является пустой граф. Любой элемент циклического пространства сам себе противоположен.

Отсюда выполнение восьми условий линейности очевидно.
[math]\triangleleft[/math]
Лемма:
Степени всех вершин всех циклов циклического пространства четны.
Доказательство:
[math]\triangleright[/math]
Рассмотрим циклический вектор [math]\sigma[/math]. Если степень какой-то вершины нечетна то в [math]\delta \sigma[/math] она входит нечетное число раз, значит [math]\delta \sigma[/math] не равно 0, что противоречит определению циклического вектора.
[math]\triangleleft[/math]
Теорема:
Размерность циклического пространства равна m - n + k, где m - число ребер графа, n - число вершин, k - число компонент связности.
Доказательство:
[math]\triangleright[/math]
Из теоремы о том, что множество фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства G следует что размерность циклического пространства равна числу ребер не входящих в каркас. Каркас содержит n - k ребер, значит размерность циклического пространства равна m - n + k.
[math]\triangleleft[/math]