|
|
| Строка 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. |
Определение
Пусть [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.
