| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| − | __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>.
| + | == Определение 1 == |
| | + | {{Определение |
| | + | |definition = |
| | + | '''Циклическое пространство графа''' — семейство множеств реберно непересекающихся циклов. <tex> C = \{ P | P \subset C_0, \forall a, b \in P \ a \ne b : a \cup b = \emptyset \} </tex>, где <math>C_0</math> — множество всех циклов графа. |
| | + | }} |
| | + | |
| | + | == Определение 2 == |
| | | | |
| | {{Определение | | {{Определение |
| | |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>. | + | '''0-цепь''' — линейная комбинация <tex>\Sigma a_{i}v_{i}</tex> где <tex>a_{i} \in F_2, v_{i} \in V</tex>, где <tex> V</tex> — множество вершин графа. |
| | + | }} |
| | + | {{Определение |
| | + | |definition = |
| | + | '''1-цепь''' — линейная комбинация <tex>\Sigma a_{i}e_{i}</tex> где <tex>a_{i} \in F_2, e_{i} \in E</tex>, где Е — множество ребер графа. |
| | + | }} |
| | + | {{Определение |
| | + | |definition = |
| | + | '''Граничный оператор <tex>\delta</tex>''' — линейный оператор,сопоставляющий 1-цепи 0-цепь таким образом, что если e = (u, v) то <tex>\delta e = u + v</tex>. Сложение производится по модулю два. Результат действия граничного оператора на 1-цепь называется границей 1-цепи. Таким образом, границей 1-цепи является сумма вершин инциндентных нечетному числу ребер из 1-цепи. |
| | }} | | }} |
| − |
| |
| | {{Определение | | {{Определение |
| | |definition = | | |definition = |
| − | '''Обобщенный цикл графа <tex> G </tex>''' (англ. ''generalized graph cycle'') {{---}} элемент линейного пространства <tex>C </tex> | + | '''Циклический вектор''' — 1-цепь с границей 0. |
| | + | }} |
| | + | {{ |
| | + | |definition = |
| | + | '''Циклическое пространство графа''' — пространство образованное множеством всех циклических векторов над полем <tex>F_2</tex> = {0,1}. |
| | + | }} |
| | + | == Эквивалентность определений == |
| | + | {{Теорема |
| | + | |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> 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> является циклом. Так как каждое ребро графа встречается не более одного раза, значит эти циклы будут реберно непересекающимися. |
| | }} | | }} |
| | | | |
| − | | + | == Свойства == |
| | + | {{Теорема |
| | + | |statement = |
| | + | Циклическое пространство графа линейно. |
| | + | |proof = |
| | + | В циклическом пространстве графа задано сложение по модулю два. |
| | + | Нейтральным элементом относительно сложения является пустой граф. |
| | + | Любой элемент циклического пространства сам себе противоположен. |
| | + | Отсюда выполнение восьми условий линейности очевидно. |
| | + | }} |
| | {{Лемма | | {{Лемма |
| − | |id = lemma1
| + | |statement = |
| − | |statement= | + | Степени всех вершин всех циклов циклического пространства четны. |
| − | Пространство <tex> C </tex> изоморфно <tex> T </tex>, где <tex> T </tex>{{---}} пространство, элементами которого являются наборы [[Основные_определения_теории_графов#def_graph_edge_1 | ребер]], из которых можно составить несколько простых реберно непересекающихся [[Основные_определения_теории_графов#def_graph_cycle_1 | циклов]].
| + | |proof = |
| − | |proof= | + | Рассмотрим циклический вектор <tex>\sigma</tex>. Если степень какой-то вершины нечетна то в <tex>\delta \sigma</tex> она входит нечетное число раз, значит <tex>\delta \sigma</tex> не равно 0, что противоречит определению циклического вектора. |
| − | Рассмотрим <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> 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= | + | |statement = |
| − | <tex> \operatorname {dim}(C) = m - n + k </tex>
| + | Размерность циклического пространства равна m - n + k, где m - число ребер графа, n - число вершин, k - число компонент связности. |
| − | |proof=
| + | |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>, то он будет ЛЗ
| + | Из теоремы о том, что множество [[Фундаментальные циклы графа|фундаментальных циклов]] относительно любого каркаса T графа G образует базис циклического пространства G следует что размерность циклического пространства равна числу ребер не входящих в каркас. Каркас содержит n - k ребер, значит размерность циклического пространства равна m - n + k. |
| − | | |
| − | {{Утверждение
| |
| − | |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>
| |
| | }} | | }} |
| − | | + | == Литература == |
| − | == Применение == | + | Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4. |
| − | Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Карпов В.Д. Теория графов - с.281 - Применения циклического пространства графа]</ref>.
| |
| − | | |
| − | == См. также ==
| |
| − | *[[Линейный_оператор|Линейный оператор]]
| |
| − | | |
| − | *[[Ядро_и_образ_линейного_оператора|Ядро и образ линейного оператора]]
| |
| − | | |
| − | == Примечания ==
| |
| − | <references/>
| |
| − | | |
| − | == Источники информации ==
| |
| − | *Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.54. — ISBN 978-5-397-00622-4
| |
| − | | |
| − | *Карпов В.Д. Теория графов - с.281
| |
| − | | |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Основные определения теории графов]]
| |
