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

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

Текущая версия на 22:08, 20 октября 2016

Циклическое пространство графа[править]

Пусть [math] m = |E(G)| [/math], [math] n = |V(G)| [/math], [math] k [/math] — количество компонент связности [math] G [/math].

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


Определение:
Циклическое пространство графа (англ. cyclic graph space) — [math] C = \operatorname {Ker}(I) [/math], где [math] I : B^m \rightarrow B^n [/math] — линейный оператор, сопоставленный матрице инцидентности [math] A [/math] графа [math] G [/math].


Определение:
Обобщенный цикл графа [math] G [/math] (англ. generalized graph cycle) — элемент линейного пространства [math]C [/math]


Лемма:
Пространство [math] C [/math] изоморфно [math] T [/math], где [math] T [/math]— пространство, элементами которого являются наборы ребер, из которых можно составить несколько простых реберно непересекающихся циклов.
Доказательство:
[math]\triangleright[/math]

Рассмотрим [math] x \in C [/math].

Рассмотрим граф [math] G_1(V_1,E_1) [/math], где [math] E_1 [/math] — множество ребер, таких, что на соответствующих местах вектора [math] x [/math] стоят единицы, а [math] V_1 = V(G) [/math] .

В силу определения обобщенного цикла: [math] \forall v : v \in V_1 ~ deg(v) \equiv 0\mod~2 [/math].

Покажем по индукции, что [math] G [/math] можно декомпозировать на несколько реберно непересекающихся простых циклов. Ведем индукцию по числу ребер. База индукции [math] |E_1(G)|=0 [/math] очевидно выполняется. Рассмотрим [math] G_1 [/math]. [math] \forall v : v \in V_1 ~ deg(v) \equiv 0\mod~2 \Rightarrow |E_1(G)| \gt |V(G)| - 1 \Rightarrow [/math] существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф.

Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.

Если рассмотреть набор реберно непересекающихся простых циклов некоторого графа [math]G[/math] и взять все ребра, принадлежащие этим циклам, то им можно сопоставить обобщенный цикл, поставив [math] 1 [/math] в соответствующие места [math] x [/math], во все остальные [math] 0 [/math].

Утверждение:
Если [math]\textbf{C}[/math] — обобщенный цикл, соответствующий простому циклу [math]C'[/math] графа [math]G[/math], то [math]I(\textbf{C}) = 0[/math]
[math]\triangleright[/math]

Пусть [math]\textbf{C}[/math] — обобщенный цикл из условия, а [math]C'[/math] — соответствующий ему простой цикл.

Тогда [math]I(\textbf{C}) = \bigoplus\limits_{e \in C'}c(e)[/math], где [math]c(e)[/math]— столбец в матрице инцидентности графа [math]G[/math], соответствующий ребру [math]e[/math]. Так как каждая вершина в [math]C'[/math] имеет степень [math] 2 [/math], то для любого [math]i \in \overline{0, |VG| - 1}[/math] верно [math]|\{e \in C': c(e)_i = 1\}| = 2[/math], а значит [math]I(\textbf{C})_i = 1 \oplus 1 = 0[/math]. Таким образом [math]I(\textbf{C}) = 0[/math].
[math]\triangleleft[/math]
В силу линейности оператора [math] I [/math] и того, что [math]I( [/math] простой цикл [math] )=0 [/math], получаем что [math] Ix=0 [/math]
[math]\triangleleft[/math]

Размерность линейного пространства обобщенных циклов[править]

Теорема:
[math] \operatorname {dim}(C) = m - n + k [/math]
Доказательство:
[math]\triangleright[/math]

[math] \operatorname {dim}(C)=\operatorname {dim}(\operatorname {Ker}(I))=m-\operatorname {Rang}(A) [/math], где [math] \operatorname {Rang}(A) [/math] — максимальное количество ЛНЗ столбцов [math] A [/math]. Если рассмотреть простой цикл [math]C[/math] в [math] G [/math], то сумма столбцов соответствующих этим ребрам равна [math]0[/math], т. к. значение оператора [math]I[/math] на соответствующем обобщенном цикле в точности равно сумме этих столбцов. Значит, эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из [math] A [/math], то он будет ЛЗ

Утверждение:
Если подмножество ребер из [math]G[/math] не содержит цикл, то набор соответствующих столбцов из [math]A[/math] ЛНЗ.
[math]\triangleright[/math]
Пусть он ЛЗ, значит существует равная нулю линейная комбинация столбцов, где не все коэффициенты равны нулю. Возьмем столбцы, коэффициенты при которых не нулевые, тогда их линейная комбинация образует [math]x \in C[/math], а значит соответствующие столбцам ребра разбиваются на простые циклы и исходное множество ребер содержало цикл. Противоречие.
[math]\triangleleft[/math]

Максимальное число ребер, которые мы можем выделить из G и которые не содержат цикл равно [math] n - k [/math] (в каждой компоненте связности выделим остовное дерево).

Итого: [math] \operatorname {dim}(C)=m - n + k [/math]
[math]\triangleleft[/math]

Применение[править]

Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа[1].

См. также[править]

Примечания[править]

Источники информации[править]

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