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

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